bluuebunny/crossref_metadata_2025_split huggingface dataset:
Extremal subgraphs of random graphs
Authors: Babai László , Simonovits Miklós , Spencer Joel 
Published: May 2007

AbstractWe shall prove that if L is a 3‐chromatic (so called “forbidden”) graph, and —Rn is a random graph on n vertices, whose edges are chosen independently, with probability p, and —Bn is a bipartite subgraph of Rn of maximum size, —Fn is an L‐free subgraph of Rn of maximum size, then (in some sense) Fn and Bn are very near to each other: almost surely they have almost the same number of edges, and one can delete Op(1) edges from Fn to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, Fn is almost surely bipartite.
Graphs with the balas—uhry property
Authors: Kano M. , Poljak S. 
Published: May 2007

AbstractWe characterize graphs H with the following property: Let G be a graph and F be a subgraph of G such that (i) each component of F is isomorphic to H or K2, (ii) the order of F is maximum, and (iii) the number of H‐components in F is minimum subject to (ii). Then a maximum matching of F is also a maximum matching of G. This result is motivated by an analogous property of fractional matchings discovered independently by J. P. Uhry and E. Balas.
On the bipartite density of regular graphs with large girth
Authors: Zýka Ondřej 
Published: May 2007

AbstractLet B(G) be the edge set of a bipartite subgraph of a graph G with the maximum number of edges. Let bk = inf{|B(G)|/|E(G)‖G is a cubic graph with girth at least k}. We will prove that limk → ∞ bk ≥ 6/7.
Covering contractible edges in 3‐connected graphs. I: Covers of size three are cutsets
Authors: Saito Akira 
Published: May 2007

AbstractAn edge of a 3‐connected graph is said to be contractible if its contraction results in a 3‐connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (Scientia (A) 2 (1988) 101–105) that the set of contractible edges in a 3‐connected graph cannot be covered by two vertices, and extended this result to a three‐vertex covering. We also study the existence of a contractible edge whose contraction preserves a specified cycle, and show that a non‐hamiltonian 3‐connected graph has a contractible edge whose contraction preserves the circumference.
Perfect path double covers in every simple graph
Authors: Li Hao 
Published: May 2007

AbstractWe prove in this paper that every simple graph G admits a perfect path double cover (PPDC), i.e., a set of paths of G such that each edge of G belongs to exactly two of the paths and each vertex of G is an end of exactly two of the paths, where a path of length zero is considered to have (identical) ends. This was conjectured by A. Bondy in 1988.
Ramsey graphs cannot be defined by real polynomials
Authors: Alon Noga 
Published: May 2007

AbstractLet P(x,y,n) be a real polynomial and let {Gn} be a family of graphs, where the set of vertices of Gn is {1,2,…,n} and for 1 ≤ i < j ≤ n {i,j} is an edge of Gn iff P(i,j,n) > 0. Motivated by a question of Babai, we show that there is a positive constant c depending only on P such that either Gn or its complement Gn contains a complete subgraph on at least c21/2√log n vertices. Similarly, either Gn or Gn contains a complete bipartite subgraph with at least cn1/2 vertices in each color class. Similar results are proved for graphs defined by real polynomials in a more general way, showing that such graphs satisfy much stronger Ramsey bounds than do random graphs. This may partially explain the difficulties in finding an explicit construction for good Ramsey graphs.
Balanced graphs with edge density constraints
Authors: Sheehan John 
Published: May 2007

AbstractSuppose that G is a finite simple graph with |V(G)| = 2n (n ≠ 3). a partition (X,Y) of V(G) is balanced if(i) |X| = |Y| = n,(ii) δ(X) ≥ 1, δ(Y) ≥ 1.Where δ(X) is the minimum degree of the induced subgraph 〈X〉 with vertex set X.We prove that if |E(G)| ≥ (n2 + n + 2)/2 and G is connected, then G contains a balanced partition. The result is sharp.
Dense bipartite digraphs
Authors: Fiol M. A. , Yebra J. L. A. 
Published: May 2007

AbstractFor its implications in the design of interconnection networks, it is interesting to find(a) (di)graphs with given maximum (out‐)degree d and diameter D that have large order;(b) (di)graphs of given order and maximum (out‐)degree d that have small diameter.(Di)graphs of either type are often called dense.This paper considers the case of bipartite digraphs. For problem (a) it is shown that a Moore‐like bound on the order of such digraphs can be (and in fact is) attained only when D ≤ 4. For D > 4 a construction is presented that yields a family of bipartite digraphs with order larger than (d4 — 1)/d4 times the above‐mentioned bound. For problem (b) an appropriate lower bound is derived and a construction is presented that provides bipartite digraphs of any (even) order whose diameter does not exceed this lower bound in more than one.
The 3‐connected graphs having a longest cycle containing only three contractible edges
Authors: Aldred R. E. L. , Hemminger Robert L. , Ota Katsuhiro 
Published: May 2007

AbstractIt is shown that with one small exception, the 3‐connected graphs admitting longest cycles that contain less than four contractible edges of the parent graph are the members of three closely related infinite families. © 1993 John Wiley & Sons, Inc.
Cycles containing all vertices of maximum degree
Authors: Broersma H. J. , Van Heuvel J. Den , Jung H. A. , Veldman H. J. 
Published: May 2007

AbstractFor a graph G and an integer k, denote by Vk the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2‐connected graph of order n with n ≤ 3k ‐ 2 and |Vk| ≤ k, then G has a cycle containing all vertices of Vk. It is shown that the upper bound k on |Vk| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |Vk| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost‐generalization of Jackson's Theorem that every 2‐connected k‐regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc.
On chromatic uniqueness of two infinite families of graphs
Authors: Dong Feng‐Ming 
Published: May 2007

AbstractIn this paper, it is proven that for each k ≥ 2, m ≥ 2, the graph Θk(m,…,m), which consists of k disjoint paths of length m with same ends is chromatically unique, and that for each m, n, 2 ≤ m ≤ n, the complete bipartite graph Km,n is chromatically unique. © 1993 John Wiley & Sons, Inc.
Laplace eigenvalues and bandwidth‐type invariants of graphs
Authors: Juvan Martin , Mohar Bojan 
Published: May 2007

AbstractFor (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min‐sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min‐sums of random graphs, random regular graphs, and Kneser graphs. © John Wiley & Sons, Inc.
Connectivity, graph minors, and subgraph multiplicity
Authors: Eppstein David 
Published: May 2007

AbstractIt is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three‐connected. We generalize these results to similarly characterize certain other minor‐closed families of graphs; in particular, G occurs O(n) times as a subgraph of the Kb,c‐free graphs, b ≥ c and c ≤ 4, iff G is c‐connected. Our results use a simple Ramsey‐theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.
On the greedoid polynomial for rooted graphs and rooted digraphs
Authors: McMahon Elizabeth W. 
Published: May 2007

AbstractWe examine some properties of the 2‐variable greedoid polynomial f(G·,t,z) when G is the branching greedoid associated to a rooted graph or a rooted directed graph. For rooted digraphs, we show a factoring property of f(G·,t,z) determines whether or not the rooted digraph has a directed cycle. © 1993 John Wiley & Sons, Inc.
The existence of k‐to‐1 continuous maps between graphs when k is sufficiently large
Authors: Hilton A. J. W. 
Published: May 2007

AbstractJo Heath and the author found a set of necessary and sufficient conditions for the existence of an exactly k‐to‐1 map from a graph G to a graph H. These conditions were all local ones. Here this result is used to give necessary and sufficient conditions for the existence of an exactly k‐to‐1 map from G to H when k is sufficiently large. The conditions for this are global in nature. © 1993 John Wiley & Sons, Inc.
Almost all trees share a complete set of immanantal polynomials
Authors: Botti Phillip , Merris Russell 
Published: May 2007

AbstractLet χ be an irreducible character of the symmetric group Sn. For an n‐by‐n matrix A = (aij), define
equation image
If G is a graph, let D(G) be the diagonal matrix of its vertex degrees and A(G) its adjacency matrix. Let y and z be independent indeterminates, and define L(G) = yD(G) + zA(G). Suppose tn is the number of trees on n vertices and sn is the number of such trees T for which there exists a nonisomorphic tree T̃ such that dχ(xl ‐ L(T)) = dx(xl ‐ L(T̃)) for every irreducible character χ of Sn. Then limn→∞ Sn/tn = 1. © 1993 John Wiley & Sons, Inc.
Hexagon‐free subgraphs of hypercubes
Authors: Conder Marston 
Published: May 2007

AbstractIt is shown (for all n ≥ 3) that the edges of the n‐cube can be 3‐colored in such a way that there is no monochromatic 4‐cycle or 6‐cycle. © 1993 John Wiley & Sons, Inc.
Collapsible graphs and matchings
Authors: Chen Zhi‐Hong , Lai Hong‐Jian 
Published: May 2007

AbstractA graph G is collapsible if for every even subset R ⊆ V(G), there is a spanning connected subgraph of G whose set of odd degree vertices is R. A graph is reduced if it does not have nontrivial collapsible subgraphs. Collapsible and reduced graphs are defined and studied in [4]. In this article, we obtain a lower bound on the size of a maximum matching in a reduced graph. As an application, we verify and strengthen the Benhocine, Clark, Köhler, and Veldman conjecture [1], when restricted to 3‐edge‐connected graphs, by showing that for n large, a simple graph G with order n and with k′(G) ≥ 3 is collapsible or is contractible to the Petersen graph if for each edge uv ∈ E(G), d(u) + d(v) ≥ (n/5) − 2. We also characterize the extremal graphs. © 1993 John Wiley & Sons, Inc.
Generating all 3‐connected 4‐regular planar graphs from the octahedron graph
Authors: Broersma H. J. , Duijvestijn A. J. W. , Göbel F. 
Published: May 2007

AbstractWe prove that all 3‐connected 4‐regular planar graphs can be generated from the Octahedron Graph, using three operations. We generated these graphs up to 15 vertices inclusive. Moreover, by including a fourth operation we obtain an alternative to a procedure by Lehel to generate all connected 4‐regular planar graphs from the Octahedron Graph. © 1993 John Wiley & Sons, Inc.
A note on maximal triangle‐free graphs
Authors: Goddard Wayne , Kleitman Daniel J. 
Published: May 2007

AbstractWe show that a maximal triangle‐free graph on n vertices with minimum degree δ contains an independent set of 3δ − n vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. © 1993 John Wiley & Sons, Inc.
On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs
Authors: Cnrs Jean‐Claude Bermond , Hell Pavol 
Published: May 2007

AbstractMotivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in‐ and outdegree d have arc‐chromatic index 2d. In order to do this, we introduce the concept of even 1‐factorizations. An even 1‐factor of a digraph is a spanning subgraph consisting of vertex disjoint loops and even cycles; an even 1‐factorization is a partition of the arcs into even 1‐factors. We prove that if a digraph admits an even 1‐factorization, then so does its line digraph. (In fact, we show that the line digraph admits an even 1‐factorization even under a weaker assumption discussed below.) As a consequence, we derive the above property of the Kautz and de Bruijn digraphs relevant to packet radio networks. © 1993 John Wiley & Sons, Inc.
Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
Authors: Woodall D. R. 
Published: May 2007

AbstractZarankiewicz's conjecture, that the crossing number of the complete‐bipartite graph Km, n is [1/2 m] [1/2 (m] −1) [1/2 n] [1/2 (n −1)], was proved by Kleitman when min(m, n) ≤ 6, but was unsettled in all other cases. The cyclic‐order graph COn arises naturally in the study of this conjecture; it is a vertex‐transitive harmonic diametrical (even) graph. In this paper the properties of cyclic‐order graphs are investigated and used as the basis for computer programs that have verified Zarankiewicz's conjecture for K7,7 and K7,9; thus the smallest unsettled cases are now K7,11 and K9,9. © 1993 John Wiley & Sons, Inc.
Disjoint Hamiltonian cycles in fan 2k‐type graphs
Authors: Sanming Zhou 
Published: May 2007

AbstractIt is conjectured that a 2(k + 1)‐connected graph of order p contains k + 1 pairwise disjoint Hamiltonian cycles if no two of its vertices that have degree less than 1/2 + 2k are distance two apart. This is proved in detail for k = 1. Similar arguments establish the conjecture for k = 2. © 1993 John Wiley & Sons, Inc.
An upper bound for the Folkman number F(3, 3; 5)
Authors: Erickson Martin 
Published: May 2007

AbstractLet F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green‐red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.
The projective plane crossing number of C3 × Cn
Authors: Riskin Adrian 
Published: May 2007

AbstractIn this paper, we show that the projective plane crossing number of the graphs C3 × Cn is n ‐ 1 for n ≤ 5 and 2 for n = 4. As far as we can tell from the literature, this is the first infinite family of graphs whose crossing number is known on a single surface other than the plane. © 1993 John Wiley & Sons, Inc.
Sufficient conditions for equality of connectivity and minimum degree of a graph
Authors: Topp Jerzy , Volkmann Lutz 
Published: May 2007

AbstractFor a graph G, let n(G), κ(G) and δ(G) denote the order, the connectivity, and the minimum degree of G, respectively. The paper contains some conditions on G implying κ(G) = δ(G). One of the conditions is that n(G) ≤ δ(G)(2p −1)/(2p −3) if G is a p‐partite graph. © 1993 John Wiley & Sons, Inc.
A sufficient condition for a regular graph to be class 1
Authors: Hilton A. J. W. , Zhao Cheng 
Published: May 2007

AbstractThe core GΔ of a simple graph G is the subgraph induced by the vertices of maximum degree. It is well known that the Petersen graph is not 1‐factorizable and has property that the core of the graph obtained from it by removing one vertex has maximum degree 2. In this paper, we prove the following result. Let G be a regular graph of even order with d(G) ≥ 3. Suppose that G contains a vertex ν such that the core of G\ν has maximum degree 2. If G is not the Petersen graph, then G is 1‐factorizable. © 1993 John Wiley & Sons, Inc.
On tree factorizations of Kn
Authors: Yu Min‐Li 
Published: May 2007

AbstractIn this paper we exhibit a class of trees with the property that if Tk is a tree on k vertices that belongs to this class, then necessary and sufficient conditions for Kn to have a Tk‐factorization are simply n = 0 (mod k) and n = 1 (mod 2(k ‐ 1)). (This class is large and in particular contains all caterpillars with an odd number of vertices.) As a corollary we obtain necessary and sufficient conditions for the existence of a K1,k‐1‐factorization of Kn, which previously had only been known to be asymptotically sufficient. © 1993 John Wiley & Sons, Inc.
On the minimum number of edge‐disjoint complete m‐partite subgraphs into which Kn can be decomposed
Authors: Huang Qing‐Xue 
Published: May 2007

AbstractLet αm(n) denote the minimum number of edge‐disjoint complete m‐partite subgraphs into which Kn can be decomposed. In [2] the author proved that when m ≥ 3, if (i) n ≡ m and n ≡ m (mod m −1), or (ii) b ∈ [2, m −1], n ≥ b(m −1) + m − (b −1), and n ≡ b(m −1) + m − (b −1) (mod m− 1), then αm(n) = ⌊(n + m −3)/(m −1)⌋ (= ⌊(n −1)/(m −1)⌋), and that for every integer n, if Kn has an edge‐disjoint complete m‐partite subgraph decomposition, then αm(n) ≥ ⌊(n− 1)/(m− 1)⌋.In this paper we generally discuss the question as to which integers n's satisfy (or do not) αm(n) = ⌊(n −1)/(m −1)⌋. Here we also study the methods to find these integers; the methods are themselves interesting. Our main results are Theorem 2.11, 2.12, and 2.16. Besides, Theorem 2.4 and 2.6 are interesting results too. © 1993 John Wiley & Sons, Inc.
Reconstructing the number of copies of a valency‐labeled finite graph in an infinite graph
Authors: King A. J. H. , Nash‐Williams C. St. J. A. 
Published: May 2007

AbstractSuppose that G, H are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that G ‐ ξ ≅ H ‐ Ψ(ξ) for every ξ ∼ V(G). Let J be a finite graph and /(π) be a cardinal number for each π ≅ V(J). Suppose also that either /(π) is infinite for every π ≅ V(J) or J has a connected subgraph C such that /(π) is finite for every π ≅ V(C) and every vertex in V(J)/V(C) is adjacent to a vertex of C. Let (J, I, G) be the set of those subgraphs of G that are isomorphic to J under isomorphisms that map each vertex π of J to a vertex whose valency in G is /(π). We prove that the sets (J, I, G), m(J, I, H) have the same cardinality and include equal numbers of induced subgraphs of G, H respectively.
Radius two trees specify χ‐bounded classes
Authors: Kierstead H. A. , Penrice S. G. 
Published: May 2007

AbstractA class of graphs χ is said to be χ‐bounded, with χ‐binding function f, if for all G ϵ Γ, χ (G) ≦ f (ω(G)), where χ(G) is the chromatic number of G and ω(G) is the clique number of G. It has been conjectured that for every tree T, the class of graphs that do not induce T is χ‐bounded. We show that this is true in the case where T is a tree of radius two.
On zero sum Ramsey numbers: Multiple copies of a graph
Authors: Bialostocki A. , Dierker P. 
Published: May 2007

AbstractAs a consequence of our main result, a theorem of Schrijver and Seymour that determines the zero sum Ramsey numbers for the family of all r‐hypertrees on m edges and a theorem of Bialostocki and Dierker that determines the zero sum Ramsey numbers for r‐hypermatchings are combined into a single theorem. Another consequence is the determination of zero sum Ramsey numbers of multiple copies of some small graphs.
Smallest (1, 2)‐eulerian weight and shortest cycle covering
Authors: Zhao Cheng 
Published: May 2007

AbstractThe concept of a (1, 2)‐eulerian weight was introduced and studied in several papers recently by Seymour, Alspach, Goddyn, and Zhang. In this paper, we proved that if G is a 2‐connected simple graph of order n (n ≧ 7) and w is a smallest (1, 2)‐eulerian weight of graph G, then |Ew=even | n ‐ 4, except for a family of graphs. Consequently, if G admits a nowhere‐zero 4‐flow and is of order at least 7, except for a family of graphs, the total length of a shortest cycle covering is at most | V(G) | + |E(G) |‐ 4. This result generalizes some previous results due to Bermond, Jackson, Jaeger, and Zhang.
Path factors of bipartite graphs
Authors: Wang Hong 
Published: May 2007

AbstractA path on n vertices is denoted by Pn. For any graph H, the number of isolated vertices of H is denoted by i(H). Let G be a graph. A spanning subgraph F of G is called a {P3, P4, P5}‐factor of G if every component of F is one of P3, P4, and P5. In this paper, we prove that a bipartite graph G has a {P3, P4, P5}‐factor if and only if i(G − S − M) ≦ 2|S| + |M| for all S ⊆ V(G) and independent M ⊆ E(G).
On greene's theorem for digraphs
Authors: Hartman Irith Ben‐Arroyo , Saleh Fathi , Hershkowitz Daniel 
Published: May 2007

AbstractGreene's Theorem states that the maximum cardinality of an optimal k‐path in a poset is equal to the minimum k‐norm of a k‐optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general digraphs in which an optimal k‐path contains a path of cardinality one. This implies the validity of the conjecture for all bipartite digraphs. We also extend Greene's Theorem to all split graphs.
On hamiltonian‐connected graphs
Authors: Gould Ronald J. , Yu Xingxing 
Published: May 2007

AbstractOne of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ≅ V(G), then G is hamiltonian‐connected. We generalize this result using set degrees. That is, for S ⊂ V(G), let deg S = |x≅S N(x)|, where N(x) = {v|xv ≅ E(G)} is the neighborhood of x. In particular we show: In a 3‐connected graph G, if deg S1 + deg S2 ≧ |V(G)| + 1 for each pair of distinct 2‐sets of vertices S1, S2 ⊂ V(G), then G is hamiltonian‐connected.Several corollaries and related results are also discussed.
Sequences realizable by maximal k‐degenerate graphs
Authors: Borowiecki M. , Ivančo J. , Mihók P. , Semanišin G. 
Published: May 2007

AbstractA graph G is called k‐degenerate if every subgraph of G has a vertex of degree at most k. A k‐degenerate graph G is maximal k‐degenerate if for every edge e ϵ E(G), G + e is not k‐degenerate. Necessary and sufficient conditions for the sequence II = (d1, d2, ⃛, dp) to be a degree sequence of a maximal k‐degenerate graph G are presented. © 1995 John Wiley & Sons, Inc.
Path covers of weighted graphs
Authors: Fan Genghua 
Published: May 2007

AbstractLet (G, w) denote a simple graph G with a weight function w : E(G) ← {0, 1, 2}. A path cover of (G, w) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex v, w(v) is the sum of the weights of the edges incident with v; v is called an odd (even) vertex if w(v) is odd (even). We prove that if every vertex of (G, w) is incident with at most one edge of weight 2, then (G, w) has a path cover P such that each odd vertex occurs exactly once, and each even vertex exactly twice, as an end of a path of P. We also prove that if every vertex of (G, w) is even, then (G, w) has a path cover P such that each vertex occurs exactly twice as an end of a path of P. © 1995 John Wiley & Sons, Inc.
An eulerian trail traversing specified edges in given order
Authors: Mao‐cheng Cai , Fleischner Herbert 
Published: May 2007

AbstractThe following results are proved in this paper. Let G be a 2k‐edge‐connected eulerian graph. (i) For every set {e1, e2, ⃛, e2k+1} ⊆ E(G) there is an eulerian trail T of the form e1, e2, ⃛, e2k+1, ⃛. (ii) For every set E* = {e1, e2, ⃛, ek} ⊆ E(G) there is an eulerian trail T = e1, ⃛, e2, ⃛, ek, ⃛ in which the elements of E* are traversed in accordance with a prescribed orientation. © 1995 John Wiley & Sons, Inc.
Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of kkn+1
Authors: Rodger C. A. , Wantland E. B. 
Published: May 2007

AbstractIn this paper we use the Hilton method of amalgamations to give a different proof of a theorem of Nash‐Williams that finds necessary and sufficient conditions for the embedding of an edge‐colored Kv into an edge‐colored Kv in which the edges of each color induce a 2‐edge‐connected k‐factor. © 1995 John Wiley & Sons, Inc.