bluuebunny/crossref_metadata_2025_split huggingface dataset:
Concept of a vertex in a matroid and 3‐connected graphs
Authors: Kelmans A. K. 
Published: May 2007

AbstractThe concept of a matroid vertex is introduced. The vertices of a matroid of a 3‐connected graph are in one‐to‐one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3‐connected graphs implies isomorphism. The concept of a vertex of a matroid leads to an equally simple proof of Whitney's theorem on the unique embedding of a 3‐connected planar graph in the sphere. It also leads to a number of new facts about 3‐connected graphs. Thus, consideration of a vertex in a matroid that is the dual of the matroid of a graph leads to a natural concept of a nonseparating cycle of a graph. Whitney's theorem on cyclic isomorphism can be strengthened (even if the nonseparating cycles of a graph are considered, the theorem is found to work) and a new criterion for planarity of 3‐connected graphs is obtained (in terms of nonseparating cycles).
Triangular embeddings of K((i‐2) n, n,…,n)
Authors: Jackson Brad 
Published: May 2007

AbstractFor complete i‐partite graphs of the form K(n1, n, n, …, n) the largest value of n1 that allows the graph to be triangularly‐embedded into a surface is (i‐2)n. In this paper the author constructs triangular embeddings into surfaces of some complete partite graphs of the form K((i‐2)n, n, …, n). The embeddings are exhibited using embedding schemes but the surfaces into which K((i‐2)n, n, …, n) are triangularly embedded can be seen to be particularly nice branched covers of a surface into which K(i‐2, 1, 1,…,1) is triangularly embedded.
Conservative graphs
Authors: Bange David W. , Barkauskas Anthony E. , Slater Peter J. 
Published: May 2007

AbstractA graph G with q edges is defined to be conservative if the edges of G can be oriented and distinctly numbered with the integers 1, 2,…, q so that at each vertex the sum of the numbers on the inwardly directed edges equals that on the outwardly directed edges. Several classes of graphs, including Kn, for n ≥4, and K2n, 2m, for n, m ≥ 2, are shown to be conservative. It is proven that the dual of a planar graceful graph is conservative, and that the converse of this result is false.
Note on the cochromatic number of several surfaces
Authors: Straight H. Joseph 
Published: May 2007

AbstractThe cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces an empty or a complete subgraph of G. In an earlier work, the author considered the problem of determining z(S), the maximum cochromatic number among all graphs that embed in a surface S. The value of z(S) was found for the sphere, the Klein bottle, and for the nonorientable surface of genus 4. In this note, some recent results of Albertson and Hutchinson are used to determine the cochromatic numbers of the projective plane and the nonorientable surface of genus 3. These results lend further evidence to support the conjecture that z(S) is equal to the maximum n for which the graph Gn = K1 U K2 U … U Kn embeds in S.
Enumeration of weak isomorphism classes of signed graphs
Authors: Sozański Tadeusz 
Published: May 2007

AbstractA signed graph is a graph in which each line has a plus or minus sign. Two signed graphs are said to be weakly isomorphic if their underlying graphs are isomorphic through a mapping under which signs of cycles are preserved, the sign of a cycle being the product of the signs of its lines. Some enumeration problems implied by such a definition, including the problem of self‐dual configurations, are solved here for complete signed graphs by methods of linear algebra over the two‐element field. It is also shown that weak isomorphism classes of complete signed graphs are equal in number to other configurations: unlabeled even graphs, two‐graphs and switching classes.
Line‐graphical degree sequences
Authors: Bauer Douglas 
Published: May 2007

AbstractA degree sequence π = (d1, d2,…,dp), with d1 ≥ d2 ≥…≥ dp, is line graphical if it is realized by the line graph of some graph. Degree sequences with line‐graphical realizations are characterized for the cases d1 = p ‐ 1, d1 = p ‐ 2, d1 ≤ 3, and d1 = dp. It is also shown that if a degree sequence with d1 = p‐1 is line graphical, it is uniquely line graphical. It follows that with possibly one exception each line‐graphical realization of an arbitrary degree sequence must have either C5, 2K1, + K2, K1 + 2K2, or 3K1, as an induced subgraph.
On ramsey numbers of forests versus nearly complete graphs
Authors: Chartrand Gary , Gould Ronald J. , Polimeni Albert D. 
Published: May 2007

AbstractA formula is presented for the ramsey number of any forest of order at least 3 versus any graph G of order n ≥ 4 having clique number n ‐ 1. In particular, if T is a tree of order m ≥ 3, then r(T, G) = 1 + (m ‐ 1)(n ‐ 2).
A Ramsey property for graph invariants
Authors: Buckley Fred 
Published: May 2007

AbstractWe consider the problem of which graph invariants have a certain property relating to Ramsey's theorem. Invariants which have this property are called Ramsey functions. We examine properties of chains of graphs associated with Ramsey functions. Methods are developed which enable one to prove that a given invariant is not a Ramsey function. Results for several familiar invariants are presented.
The λ‐complete multigraphs
Authors: Gardner M. L. 
Published: May 2007

AbstractLet E1……Em be the edges of a hypergraph. Assume each element in the union of the edges occurs in at least two of E1……Em. Assume further that every pair of distinct edges, E1, and E1, intersect in at most one element and that for each such pair there are exactly λ other edges Ek such that E1 and E1 both intersect Ek. We characterize the hypergraphs for which each |E1| ≤ 2. These are the λ‐complete multigraphs.
Chromatic numbers of hypergraphs and coverings of graphs
Authors: Miller Zevi , Müller Heinrich 
Published: May 2007

AbstractBurr recently proved [3] that for positive integers m1, m2……mk, and any graph G we have X(G)

if and only if G can be expressed as the edge disjoint union of subgraphs Fi satisfying X(Fi) ≤ mi. This theorem is generalized to hypergraphs. By suitable interpretations the generalization is then used to deduce propositions on coverings of graphs.
Meyniel's theorem for strongly (p, q) ‐ Hamiltonian digraphs
Authors: Wojda A. P. 
Published: May 2007

AbstractWe give the following theorem: Let D = (V, E) be a strongly (p + q + 1)‐connected digraph with n ≥ p + q + 1 vertices, where p and q are nonnegative integers, p ≤ n ‐ 2, n ≥ 2. Suppose that, for each four vertices u, v, w, z (not necessarily distinct) such that {u, v} ∩ {w, z} = Ø, (w, u) ∉ E, (v, z) ∉ E, we have id(u) + od(v) + od(w + id(z) ≥ 2 (n + p + q)) + 1. Then D is strongly (p, q)‐Hamiltonian.
Nonseparating cycles in K‐Connected graphs
Authors: Thomassen Carsten 
Published: May 2007

AbstractWe show that every k‐connected graph with no 3‐cycle contains an edge whose contraction results in a k‐connected graph and use this to prove that every (k + 3)‐connected graph contains a cycle whose deletion results in a k‐connected graph. This settles a problem of L. Lovász.
On an adjacency property of graphs
Authors: Exoo Geoffrey 
Published: May 2007

AbstractA graph G has property A(m, n, k) if for any sequence of m + n distinct points of G, there are at least k other points, each of which is adjacent to the first m points of the sequence but not adjacent to any of the latter n points. the minimum order among all graphs with property A(m, n, k) is denoted a(m, n, k). Bounds are given on the numbers a(m, n, k) and some exact results are indicated.
Locally homogeneous graphs from groups
Authors: Vince Andrew 
Published: May 2007

AbstractA graph is called locally homogeneous if the subgraphs induced at any two points are isomorphic. in this Note we give a method for constructing locally homogeneous graphs from groups. the graphs constructable in this way are exactly the locally homogeneous graphs with a point symmetric universal cover. As an example we characterize the graphs that are locally n‐cycles.
Constructions of covering triangulations with folds
Authors: Bouchet André 
Published: May 2007

AbstractLet G be a graph with a known triangular embedding in a surface S, and consider G(m), the composition of G with an independant set of order m. The purpose of this paper is to construct a triangular embedding of G(m) into a surface magnified image by using a covering triangulation with folds. We make the construction for three cases. One of them is used for proving that G(m) can be triangularly embedded into a surface magnified image if G is an Eulerian graph which can be triangularly embedded into a surface S with the same orientability characteristic as magnified image.
The connectivities of line and total graphs
Authors: Bauer Douglas , Tindell Ralph 
Published: May 2007

AbstractSharp lower bounds for the point connectivity and line connectivity of the line graph L(G) and the total graph T(G) of a graph G are determined. The lower bounds are expressed in terms of the point connectivity k, line connectivity λ, and minimum degree δ of G. It is also shown that 2λ is an upper bound for k(T(G)) and that λ(T(G))= 2δ = δ(T(G)). In each case the realizable values beyond the lower bound are determined.
A counterexample to a conjecture on paths of bounded length
Authors: Boyles Stephanie M. , Exoo Geoffrey 
Published: May 2007

AbstractIn a recent paper Lovász, Neumann‐Lara, and Plummer studied Mengerian theorems for paths of bounded length. Their study led to a conjecture concerning the extent to which Menger's theorem can fail when restricted to paths of bounded length. In this paper we offer counterexamples to this conjecture.
A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular‐arc graphs, and nested interval graphs
Authors: Skrien Dale J. 
Published: May 2007

AbstractGiven a set F of digraphs, we say a graph G is a F‐graph (resp., F*‐graph) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in F. It is proved that all the classes of graphs mentioned in the title are F‐graphs or F*‐graphs for subsets F of a set of three digraphs.
Nonorientable genus of cartesian products of regular graphs
Authors: Pisanski Tomaž 
Published: May 2007

AbstractA special type of surgery developed by A. T. White and later used by the author to construct orientable quadrilateral embeddings of Cartesian products of graphs is here expanded to cover the nonorientable case as well. This enables the nonorientable genus of many families of Cartesian products of triangle‐free graphs to be computed.
Generalizations of a Ramsey‐theoretic result of chvátal
Authors: Burr Stefan A. , Erdös Paul 
Published: May 2007

AbstractChvátal has shown that if T is a tree on n points then r(Kk, T) = (k – 1) (n – 1) + 1, where r is the (generalized) Ramsey number. It is shown that the same result holds when T is replaced by many other graphs. Such a T is called k‐good. The results proved all support the conjecture that any large graph that is sufficiently sparse, in the appropriate sense, is k‐good.
On the Ramsey number of trees versus graphs with large clique number
Authors: Gould Ronald J. , Jacobson Michael S. 
Published: May 2007

AbstractChvátal established that r(Tm, Kn) = (m – 1)(n – 1) + 1, where Tm is an arbitrary tree of order m and Kn is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed Kn could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that Kn can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(Tm, Kn –tK2) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where Tm is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].
On a Ramsey‐type problem
Authors: Chung F. R. K. 
Published: May 2007

AbstractSuppose a graph G has the property that if one colors the edges of G in r colors, there always exists a monochromatic triangle. Is it true that if one colors the edges of G in r + 1 colors so that every vertex is incident to at most r colors then there must be a monochromatic triangle? This problem, which was first raised by P. Erdös, is answered in the negative here.
Graphs with unique Ramsey colorings
Authors: Grossman Jerrold W. 
Published: May 2007

AbstractA pair of graphs (H1, H2) is a cleaver if there is a graph G with a unique factorization G = G2 ⊕ G2 such that Gi does not contain a copy of Hi. (In case H1 = H2, H1 is a cleaver if the factorization is unique up to interchange of factors.) A variety of positive and negative results on the existence of cleavers is obtained. For example (tree, complete graph) is a cleaver, and the triangle is the cleaver of an infinite collection of minimal graphs. On the other hand, stars are not cleavers.
On a conjecture of erdöus, simonovits, and sós concerning anti‐Ramsey theorems
Authors: Alon Noga 
Published: May 2007

AbstractFor n ≧ k ≧ 3, let f(n,Ck) denote the maximum number m for which it is possible to color the edges of the complete graph Kn with m colors in such a way that each k‐cycle Ck in Kn has atleast two edges of the same color. Erdös, Simonovits, and Sós conjectured that for every fixed k ≧ 3, f(n, Ck) = n (k–2/2 + 1/k–1) + O(1), and proved it only for k = 3. It is shown that f(n, C4) = n + [1/3n] – 1, and the conjecture thus proved for k = 4. Some upper bounds are also obtained for f(n, Ck), k ≧ 5.
Euclidean Ramsey theorems on the n‐sphere
Authors: Graham H. L. 
Published: May 2007

AbstractLet us call a finite subset X of a Euclidean m‐space Em Ramsey if for any positive integer r there is an integer n = n(X;r) such that in any partition of En into r classes C1,…, Cr, some Ci contains a set X' which is the image of X under some Euclidean motion in En. Numerous results dealing with Ramsey sets have been proved in recent years although the basic problem of characterizing the Ramsey sets remains unsettled. The strongest constraints currently known are: (i) Any Ramsey set must lie on the surface of some sphere; (ii) Any subset of the set of vertices of a rectangular parallelepiped is Ramsey. In this paper we examine the corresponding problem in the case that our underlying spaces are (unit) n‐spheres Sn and the allowed motions are orthogonal transformations of Sn onto itself. In particular, we show that for subsets of Sn which are not too “large,” results similar to (i) and (ii) hold.
On size Ramsey number of paths, trees, and circuits. I
Authors: Beck JóZsef 
Published: May 2007

AbstractThe size Ramsey number ř(G) of a graph G is the smallest integer ř such that there is a graph F of ř edges with the property that any two‐coloring of the edges of F yields a monochromatic copy of G. First we show that the size Ramsey number ř(Pn) of the path Pn of length n is linear in n, solving a problem of Erdös. Second we present a general upper bound on size Ramsey numbers of trees.
On a Quasi‐Ramsey problem
Authors: Erdös Paul , Pach János 
Published: May 2007

AbstractIt is proved that if a graph G has atleast cn log n vertices, then either G or its complement G contains a subgraph H with atleast n vertices and minimum degree atleast | V(H)|/2. This result is not far from being best possible, as is shown by a rather unusual random construction. Some related questions are also discussed.
Graph decomposition with constraints on the connectivity and minimum degree
Authors: Thomassen Carsten 
Published: May 2007

AbstractFor each pair s,t of natural numbers there exist natural numbers f(s,t) and g(s,t) such that the vertex set of each graph of connectivity at least f(s,t) (respectively minimum degree at least g(s,t)) has a decomposition into sets which induce subgraphs of connectivity (respectively minimum degree) at least s and t, respectively.
Enumeration of acyclic and unicyclic nets with four types of self‐duality
Authors: Holroyd Fred 
Published: May 2007

AbstractA net is a graph in which each point and line is given a sign. The point, line, and simple duals of a net are obtained by reversing the signs of the points, lines, or both. If a net possesses two of the three types of self‐duality, it possesses all three and is said to be doubly self‐dual. Enumeration formulas are derived for nets and point, line, simply, and doubly self‐dual nets, whose underlying graphs are acyclic and unicyclic. The numbers are tabulated up to 12 points (24 for doubly self‐dual nets) in each case.
Isomorphic factorizations of complete equipartite graphs
Authors: Quinn S. J. 
Published: May 2007

AbstractA complete equipartite graph is a complete multipartite graph such that the color classes are equinumerous. An isomorphic factorization of a graph is a partition of the line set into disjoint isomorphic parts. It is shown that an isomorphic factorization of the complete equipartite graph into t isomorphic subgraphs exists whenever the total number of lines is divisible by t.
Local connectivity of a random graph
Authors: Erdös P. , Palmer E. M. , Robinson R. W. 
Published: May 2007

AbstractA graph is locally connected if for each vertex ν of degree ≧2, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order n is p = ((3/2 +ϵn) log n/n)1/2 where ϵn = (log log n + log(3/8) + 2x)/(2 log n), then the limiting probability that a random graph is locally connected is exp(‐exp(‐x)).
Hamiltonian path graphs
Authors: Chartrand Gary , Kapoor S. F. , Nordhaus E. A. 
Published: May 2007

AbstractThe Hamiltonian path graph H(G) of a graph G is that graph having the same vertex set as G and in which two vertices u and v are adjacent if and only if G contains a Hamiltonian u‐v path. A characterization of Hamiltonian graphs isomorphic to their Hamiltonian path graphs is presented.
On Hamiltonian‐connected regular graphs
Authors: Tomescu Ioan 
Published: May 2007

AbstractIn this paper it is shown that any m‐regular graph of order 2m (m ≧ 3), not isomorphic to Km,m, or of order 2m + 1 (m even, m ≧ 4), is Hamiltonian connected, which extends a previous result of Nash‐Williams. As a corollary, it is derived that any such graph contains atleast m Hamiltonian cycles for odd m and atleast 1/2m Hamiltonian cycles for even m.
When the cartesian product of two directed cycles is hypo‐Hamiltonian
Authors: Penn Laurence E. , Witte David 
Published: May 2007

AbstractWe show that the Cartesian product Za × Zb of two directed cycles is hypo‐Hamiltonian (Hamiltonian) if and only if there is a pair of relatively prime positive integers m and n with ma + nb = ab ‐ 1 (ma + nb = ab). The result for hypo‐Hamiltonian is new; that for Hamiltonian is known. These are special cases of the fact that there is a simple circuit of length p in Za × Zb if and only if there is a pair of relatively prime non‐negative integers m and n with ma + nb = p ≤ ab.
On the existence of specified cycles in a tournament
Authors: Benhocine Abdelhamid , Wojda A. Pawel 
Published: May 2007

AbstractFor 2 ≦ p ≦n and n ≧ 3, D(n, p) denotes the digraph with n vertices obtained from a directed cycle of length n by changing the orientation of p‐ 1 consecutives edges. In this paper, we prove that every tournament of order n ≧ 7 contains D(n, p) for p = 2, 3, …, n. Furthermore, we determine the tournaments of order n, 3 ≦ n ≦ 6, which do not contain D(n, p) for some p.
Infinite median graphs, (0, 2)‐graphs, and hypercubes
Authors: Bandelt Hans‐J. , Mulder Henry Martyn 
Published: May 2007

AbstractHypercubes are characterized among connected bipartite graphs by interval conditions in several ways. These results are based on the following two facts: (i) connected bipartite graphs are median provided that all their intervals induce median graphs, and (ii) median (0, 2)‐graphs are hypercubes. No cardinality restrictions are made.
On proulx's four exceptional toroidal groups
Authors: Tucker Thomas W. 
Published: May 2007

AbstractV. K. Proulx has proved that every finite group having a Cayley graph embeddable in the torus is, with four unresolved exceptions, a quotient of a Euclidean space group. It was conjectured that these four unresolved groups are not exceptional, that they in fact are Euclidean space‐group quotients. It is shown here that one is not exceptional, but the other three are.
Rotation numbers for unions of circuits
Authors: Bollobás Béla , Cockayne E. J. , Yao Fang Zu 
Published: May 2007

AbstractLet G be a simple undirected graph which has p vertices and is rooted at x. Informally, the rotation number h(G, x) of this rooted graph is the minimum number of edges in a p‐vertex graph F, such that for each vertex v of F, there exists a copy of G in F with the root x at v. In this paper, we calculate a lower bound for the rotation number of the graph which is the disjoint union of circuits Ck, Ce where 4 ⩽ k < ⩽, give infinite classes where this bound is exact, and obtain classes of rotation numbers for the case k = 4.
J. Howard Redfield 1879–1944
Authors: Lloyd E. Keith 
Published: May 2007

AbstractDuring much of his life J. Howard Redfield earned his living as an engineer but his main interests lay elsewhere. He performed and wrote music and was a gifted linguist, familiar with almost all European languages, as well as with some African and Asian tongues. In middle age he turned his attention towards combinatorial mathematics but it was not until many years after his death that the mathematical world realized that he had obtained significant results.
Redfield's lost paper in a modern context
Authors: Hall J. I. , Palmer E. M. , Robinson R. W. 
Published: May 2007

AbstractAn alternative proof of the main results of the preceding paper by J. Howard Redfield is provided in modern terminology. The relationship of Redfield's results with a number of more recent articles is discussed. This is necessitated by the delay of over forty years between the submission and publication of his lost paper.
Regular planar graphs with faces of only two types and shortness parameters
Authors: Owens P. J. 
Published: May 2007

AbstractWe construct a small non‐Hamiltonian 3‐connected trivalent planar graph whose faces are all 4‐gons or 7‐gons and show that the shortness coefficient of the class of such graphs is less than one. Then, by transforming non‐Hamiltonian trivalent graphs into regular graphs of valency four or five, we obtain our main results, as follows. We show first that the class of 3‐connected r‐valent planar graphs whose faces are of only two types, triangles and q‐gons, contains non‐Hamiltonian members and has a shortness exponent less than one when r = 4, for all q ≧ 12. Under the extra restriction that, among graphs of connectivity three, only those with maximum cyclic edge‐connectivity are to be considered, we prove the same result also when r = 4, for q = 20, and when r = 5, for all q ≧ 14 except multiples of three.
Tutte's 5‐flow conjecture for the projective plane
Authors: Steinberg Richard 
Published: May 2007

AbstractHeawood proved that every planar graph with no 1‐cycles is vertex 5‐colorable, which is equivalent to the statement that every planar graph with no 1‐bonds has a nowhere‐zero 5‐flow. Tutte has conjectured that every graph with no 1‐bonds has a nowhere‐zero 5‐flow. We show that Tutte's 5‐Flow Conjecture is true for all graphs embeddable in the real projective plane.