bluuebunny/crossref_metadata_2025 huggingface dataset:
The longest cycle of a graph with a large minimal degree
Authors: Alon Noga
Published: May 2007

We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k − 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.
On q‐trees
Authors: Chao Chong‐Yun , Li Nian‐Zu , Xu Shao‐Ji
Published: May 2007

We show that a graph G with n vertices is a q‐tree if and only if its chromatic polynomial is P(G, λ) = λ(λ – 1) ⃛ (λ – q + 1) (λ – q)n‐q where n ≥q.
A generalization of edge‐coloring in graphs
Authors: Louis Hakimi S. , Kariv Oded
Published: May 2007

Bounds are given on the number of colors required to color the edges of a graph (multigraph) such that each color appears at each vertex v at most m(ν) times. The known results and proofs generalize in natural ways. Certain new edge‐coloring problems, which have no counterparts when m(ν) = 1 for all ν ϵ V, are studied.
On digraphs with the odd cycle property
Authors: Manber Rachel , Shao Jia‐Yu
Published: May 2007

We say that a digraph D has the odd cycle property if there exists an edge subset S such that every cycle of D has an odd number of edges from S. We give necessary and sufficient conditions for a digraph to have the odd cycle property. We also consider the analogous problem for graphs.
On iterated clique graphs with increasing diameters
Authors: Peyrat C. , Rall D. F. , Slater P. J.
Published: May 2007

We examine the problem of finding a graphGwhosenth iterated clique graph has diameter equal to the diameter ofGplusn.
Existence of graphs with prescribed mean distance
Authors: Hendry G. R. T.
Published: May 2007

It is shown that for each rational number t ≥ 1 there exist infinitely many graphs with mean distance equal to t.

For a graph G, define the mean distance μ(G) by

.

In an earlier issue of this journal, J. Plesník [3, Theorem 9] showed that, given real numbers t ≥ 1 and ϵ > 0, there exists a graph G with |μ(G)−t| < ϵ. Furthermore, he asked [3, p. 19]: Given a rational number t ≥ 1, does there exist a graph G with μ(G) = t? We answer this question in the affirmative by proving:
Node coverings with odd chains
Authors: De Werra D.
Published: May 2007

A min‐max theorem for node coverings with odd chains in bipartite graphs is derived by simple network flow techniques. A characterization of minimum node covering in terms of a special kind of alternating chains is given, an extension of a result of Norman and Rabin on matchings and node coverings by edges is obtained.
Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs
Authors: Pritikin Dan
Published: May 2007

Graham and Pollak [2] proved that n – 1 is the minimum number of edge‐disjoint complete bipartite subgraphs into which the edges of Kn decompose. Tverberg [6], using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcs/edges of complete digraphs/multigraphs into a minimum number of arc/edge‐disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee [4]. We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct vertices.
Saturated graphs with minimal number of edges
Authors: Kászonyi L. , Tuza Zs.
Published: May 2007

Let F = {F1,…} be a given class of forbidden graphs. A graph G is called F‐saturated if no Fi ∈ F is a subgraph of G but the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F‐saturated graphs is examined. General estimations are given and the structure of minimal graphs is described for some special forbidden graphs (stars, paths, m pairwise disjoint edges).
Orientations of hamiltonian cycles in large digraphs
Authors: Wojda Adam Paweł
Published: May 2007

We prove that, with some exceptions, every digraph with n ≥ 9 vertices and at least (n – 1) (n – 2) + 2 arcs contains all orientations of a Hamiltonian cycle.
Some large graphs with given degree and diameter
Authors: Alegre I. , Fiol M. A. , Yebra J. L. A.
Published: May 2007

This paper considers the (Δ, D) problem: to maximize the order of graphs with given maximum degree Δ and diameter D, of importance for its implications in the design of interconnection networks. Two cubic graphs of diameters 5 and 8 and orders 70 and 286, respectively, and a graph of degree 5, diameter 3 and order 66 are presented, which improve the previously known orders for these values of Δ and D. By its construction, these graphs have a large automorphism group.
Even graphs
Authors: Göbel F. , Veldman H. J.
Published: May 2007

A nontrivial connected graph G is called even if for each vertex v of G there is a unique vertex v such that d(v, v) = diam G. Special classes of even graphs are defined and compared to each other. In particular, an even graph G is called symmetric if d(u, v) + d(u, v) = diam G for all u, v ∈ V(G). Several properties of even and symmetric even graphs are stated. For an even graph of order n and diameter d other than an even cycle it is shown that n ≥ 3d – 1 and conjectured that n ≥ 4d – 4. This conjecture is proved for symmetric even graphs and it is shown that for each pair of integers n, d with n even, d ≥ 2 and n ≥ 4d – 4 there exists an even graph of order n and diameter d. Several ways of constructing new even graphs from known ones are presented.
Strongly balanced graphs and random graphs
Authors: Ruciński Andrzej , Vince Andrew
Published: May 2007

The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with v vertices and e edges if and only if I ν – 1 ⩽ e ⩽(). This result is applied to a classic question of Erdös and Rényi: What is the probability that a random graph on n vertices contains a given graph? A rooted version of this problem is also solved.
An Eulerian trail through Königsberg
Authors: Wilson Robin J.
Published: May 2007

We look back 250 years to the origins of graph theory when Euler presented a paper on the solution of the Königsberg bridges problem.
An Eulerian exposition
Authors: Lesniak Linda , Oellermann Ortrud R.
Published: May 2007

An overview of Eulerian graphs is presented. In particular, characterizations of Eulerian graphs and digraphs as well as algorithms for constructing Eulerian circuits are discussed. A solution to the Chinese postman problem is followed by a study of subgraphs and supergraphs of Eulerian graphs. After an introduction to randomly Eulerian graphs and digraphs, we conclude with a summary of a variety of results involving enumeration.
What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?
Authors: Dean Nathaniel
Published: May 2007

A digraph D with n vertices is said to be decomposable into a set S of dicycles if every arc of D is contained in exactly one member of S. Counterexamples are given to the following conjectures which are generalizations of three well‐known conjectures by G. Hajós, P. Erdős, and P.J. Kelly: (1) [B. Jackson] Every eulerian‐oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{n}{2} $\end{document} dicycles. (2) [W. Bienia & H. Meyniel] Every eulerian digraph is decomposable into at most n dicycles.

Certain observations lead us to make three other conjectures: (a) Every eulerian‐oriented graph is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{2n}}{3} $\end{document} dicycles. (b) Every symmetric digraph with n > 1 is decomposable into at most 2n – 3 dicycles. (c) Every eulerian digraph with n > 1 is decomposable into at most \documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{8n}}{3} $\end{document} – 3 dicycles.
Reflections on graph theory
Authors: Thomassen Carsten
Published: May 2007

At the occasion of the 250th anniversary of graph theory, we recall some of the basic results and unsolved problems, some of the attractive and surprising methods and results, and some possible future directions in graph theory.
Desert island theorems
Authors: Beineke Lowell W.
Published: May 2007

As graph theory celebrates its 250th anniversary, this essay considers examples of various types of results which the future, it is hoped, will bring.
On unreliability polynomials and graph connectivity in reliable network synthesis
Authors: Boesch F. T.
Published: May 2007

The analysis and synthesis of reliable large‐scale networks typically involve a graph theoretic model. We give a survey of the graph theoretic notions which are relevant to the synthesis problem. It is shown how a number of unsolved graph extremal problems relate to the synthesis question.
The nonorientable genus is additive
Authors: Archdeacon Dan
Published: May 2007

A graph G is a k‐amalgamation of two graphs G1 and G2 if G = G1 ∪ G2 and G1 ∩G2 is a set of k vertices. In this paper we show that γ(G) differs from γ(G1) + γ(G2) by at most a quadratic on k, where γ denotes the nonorientable genus of a graph. In the sequel to this paper we show that no such bound holds for the orientable genus of k‐amalgamations.
The orientable genus is nonadditive
Authors: Archdeacon Dan
Published: May 2007

A graph G is a k‐amalgamation of two graphs G1 and G2 if G = G1 ∪ G2 and G1 ∩ G2 is a set of k vertices. In this paper we construct 3‐amalgamations Gn = Hn ∪ Hn such that γ(Gn) = 5n and γ(Hn) = 3n, where γ denotes the orientable genus of a graph. Thus γ(G1 ∪ G2) may differ from γ(G1) + γ(G2) by an arbitrarily large amount for amalgamations over 3 (or more) vertices. In contrast, an earlier paper shows that the nonorientable genus of a k‐amalgamation differs from the sum of the nonorientable genera of its parts by at most a quadratic on k.
The ramsey number of k5 ‐ e
Authors: Clapham C. , Exoo G. , Harborth H. , Mengersen I. , Sheehan J.
Published: May 2007

The Ramsey number r(K5 ‐ e) = 22 is proved.
Longest cycles in 3‐connected graphs contain three contractible edges
Authors: Dean Nathaniel , Hemminger Robert L. , Ota Katsuhiro
Published: May 2007

We show that if G is a 3‐connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges.
Critically cochromatic graphs
Authors: Broere Izak , Burger Marieta
Published: May 2007

A graph G is critically n‐cochromatic if (its cochromatic number) z(G) = n and z(G ‐ v) = n ‐ 1 for every vertex v of G. Properties of critically n‐cochromatic graphs are discussed and we also construct graphs that are critically n‐chromatic and critically n‐cochromatic.
Graphs without four‐cycles
Authors: Clapham C. R. J. , Flockhart A. , Sheehan J.
Published: May 2007

We investigate the values of t(n), the maximum number of edges in a graph with n vertices and not containing a four‐cycle. Techniques for finding these are developed and the values of t(n) for all n up to 21 are obtained. All the corresponding extremal graphs are found.
On the genus of the semidirect product of ℤ9 by ℤ3
Authors: Brin Matthew G. , Rauschenberg David E. , Squier Craig C.
Published: May 2007

We show that the non‐commutative semidirect product Γ of ℤ9 by ℤ3 has orientable genus 4. In other words, some Cayley graph of Γ embeds in an orientable surface of genus 4 (Euler characteristic −6), but no Cayley graph of Γ embeds in an orientable surface of genus less than 4 (Euler characteristic greater than −6). We also show that some Cayley graph of Γ embeds in a (non‐orientable) surface of Euler characteristic −3, but no Cayley graph of Γ embeds in a surface of Euler characteristic greater than −3. Γ is the first known example of a group whose orientable Euler characteristic and non‐orientable Euler characteristic differ by more than 1. Our results also complete the determination of the orientable genus of each group of order less than 32.
Independence number, connectivity, and r‐factors
Authors: Nishimura Tsuyoshi
Published: May 2007

We show that if r ⩾ 1 is an odd integer and G is a graph with |V(G)| even such that k(G) ⩾ (r + 1)2/2 and (r + 1)2α(G) ⩽ 4rk(G), then G has an r‐factor; if r ⩾ 2 is even and G is a graph with k(G) ⩾ r(r + 2)/2 and (r + 2)α(G) ⩽ 4k(G), then G has an r‐factor (where k(G) and α(G) denote the connectivity and the independence number of G, respectively).
Infinite, highly connected digraphs with no two arc‐disjoint spanning trees
Authors: Aharoni Ron , Thomassen Carsten
Published: May 2007

We present a construction of countably infinite, highly connected graphs and digraphs, which shows that several basic connectivity results on finite graphs, including Edmondsapos;s branching theorem, cannot be extended to the infinite case.
Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs
Authors: Kjær Jørgensen Leif
Published: May 2007

A probabilistic result of Bollobás and Catlin concerning the largest integer p so that a subdivision of Kp is contained in a random graph is generalized to a result concerning the largest integer p so that a subdivision of Ap is contained in a random graph for some sequence A1, A2,… of graphs such that Ai+1 contains a subdivision of Ai. A similar result is proved for subdivisions with odd paths or cycles. The result is applied to disprove a conjecture of Chartrand, Geller, and Hedetniemi. The maximum number of edges in a graph without a subdivision of Kp, p = 4, 5, with odd paths or cycles is determined.
A note on list‐colorings
Authors: Chetwynd Amanda , Häggkvist Roland
Published: May 2007

In this article we discuss the current results on the list chromatic conjecture and prove that if G is a triangle free graph with maximum degree Δ then χapos;|(G) ⩽; 9Δ/5.
Graph spanners
Authors: Peleg David , Schäffer Alejandro A.
Published: May 2007

Given a graph G = (V, E), a subgraph Gapos; = (V, Eapos;) is a t‐spanner of G if for every u, v ∈ V, the distance from u to v in Gapos; is at most t times longer than that distance in G. This paper presents some results concerning the existence and efficient constructability of sparse spanners for various classes of graphs, including general undirected graphs, undirected chordal graphs, and general directed graphs.
Is every cycle basis fundamental?
Authors: Hartvigsen David , Zemel Eitan
Published: May 2007

A collection of (simple) cycles in a graph is called fundamental if they form a basis for the cycle space and if they can be ordered such that Cj(C1 U … U Cj‐1) ≠ Ø for all j. We characterize by excluded minors those graphs for which every cycle basis is fundamental. We also give a constructive characterization that leads to a (polynomial) algorithm for recognizing these graphs. In addition, this algorithm can be used to determine if a graph has a cycle basis that covers every edge two or more times. An equivalent dual characterization for the cutset space is also given.
On the delta‐wye reduction for planar graphs
Authors: Truemper K.
Published: May 2007

We provide an elementary proof of an important theorem by G. V. Epifanov, according to which every two‐terminal planar graph satisfying certain connectivity restrictions can by some sequence of series/parallel reductions and delta‐wye exchanges be reduced to the graph consisting of the two terminals and just one edge.
Maximal antiramsey graphs and the strong chromatic number
Authors: Burr S. A. , Erdös P. , Graham R. L. , T. Sós V.
Published: May 2007

A typical problem arising in Ramsey graph theory is the following. For given graphs G and L, how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper we investigate the opposite extreme. That is, we will require that in any subgraph of G isomorphic to L, all its edges have different colors. We call such a subgraph a totally multicolored copy of L. Of particular interest to us will be the determination of Xs(n, e, L), defined to be the minimum number of colors needed to edge‐color some graph G(n, ϵ) with n vertices and e edges so that all copies of L in it are totally multicolored.

It turns out that some of these questions are surprisingly deep, and are intimately related, for example, to the well‐studied (but little understood) functions rk(n), defined to be the size of the largest subset of {1, 2,…, n} containing no k‐term arithmetic progression, and g(n; k, l), defined to be the maximum number of triples which can be formed from {1, 2,…, n} so that no two triples share a common pair, and no k elements of {1, 2,…, n} span l triples.
Irredundant ramsey numbers for graphs
Authors: Brewster R. C. , Cockayne E. J. , Mynhardt C. M.
Published: May 2007

The irredundant Ramsey number s(m, n) is the least value of p such that for any p‐vertex graph G, either G has an irredundant set of at least n vertices or its complement G has an irredundant set of at least m vertices. The existence of these numbers is guaranteed by Ramsey's theorem. We prove that s(3, 3) = 6, s(3, 4) = 8, and s(3,5) = 12.
The growth rate of the harmonious chromatic number
Authors: Beane Donald G. , Biggs Norman L. , Wilson Brian J.
Published: May 2007

In this paper we investigate the growth rate of the harmonious chromatic number of a family of regular graphs, as a function of the number of vertices, when the valency or the diameter is fixed. We also look at families of graphs where the harmonious coloring is minimal.
A decomposition for strongly perfect graphs
Authors: Olariu Stephan
Published: May 2007

A graph G is strongly perfect if every induced subgraph H of G contains a stable set that meets all the maximal cliques of H. We present a graph decomposition that preserves strong perfection: more precisely, a stitch decomposition of a graph G = (V, E) is a partition of V into nonempty disjoint subsets V1, V2 such that in every P4 with vertices in both Viapos;s, each of the three edges has an endpoint in V1 and the other in V2.

We give a good characterization of graphs that admit a stitch decomposition and establish several results concerning the stitch decomposition of strongly perfect graphs.
Edge disjoint cycles in graphs
Authors: Hao Li
Published: May 2007

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ⩾ 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ⩾ 2δ2, then for any 3 ⩽ l1 ⩽ l2 ⩽ ⃛ ⩽ lk ⩽ n, 1 = k = [(δ ‐ 1)/2], such graph has K edge disjoint cycles with lengths l1, l2…lk, respectively. In particular, when l1 = l2 = ⃛ = lk = n and k = [(δ ‐ 1)/2], the graph contains [(δ ‐ 1)/2] edge disjoint hamiltonian cycles.
Covering the vertices of a graph by cycles of prescribed length
Authors: Amar D. , Fournier I. , Germa A.
Published: May 2007

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n2 ‐ 3n + 6)/2. For any integers k, n1, n2,…,nk such that n = n1 + n2 +. + nk and ni ⩾ 3, there exists a covering of the vertices of G by disjoint cycles (Ci) =l…k with |Ci| = ni, except when n = 6, n1 = 3, n2 = 3, and G is isomorphic to G1, the complement of G1 consisting of a C3 and a stable set of three vertices, or when n = 9, n1 = n2 = n3 = 3, and G is isomorphic to G2, the complement of G2 consisting of a complete graph on four vertices and a stable set of five vertices.

We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n2 ‐ n + 2. For any integers s, n1, n2,…,ns with ni ⩾ 2 and n = n1 + n2 + ⃛ + ns, there exists a covering of the vertices of G by s disjoint cycles Ci, with |Ci| = 2ni.
The effects of distance and neighborhood union conditions on hamiltonian properties in graphs
Authors: Lindquester Terri England
Published: May 2007

We prove that a 2‐connected graph G of order p is hamiltonian if for all distinct vertices u and v, dist(u,v) = 2 implies that |N(u) U N(v)| ⩾ (2p ‐ 1)/3. We also demonstrate hamiltonian‐connected and traceability properties in graphs under similar conditions.
The number of bipartite tournaments with a unique given factor
Authors: Manolis Manoussakis , Yannis Manoussakis
Published: May 2007

We give a recursive function in order to calculate the number of all non‐isomorphic bipartite tournaments containing an unique hamiltonian cycle. Using this result we determine the number of all nonisomorphic bipartite tournaments that admit an unique factor isomorphic to a given 1‐diregu‐lar bipartite graph.
The minimum number of triangles covering the edges of a graph
Authors: Lehel Jenö
Published: May 2007

Suppose that a connected graph G has n vertices and m edges, and each edge is contained in some triangle of G. Bounds are established here on the minimum number tmin(G) of triangles that cover the edges of G.

We prove that ⌈(n ‐ 1)/2⌉ ⩽ tmin(G) with equality attained only by 3‐cactii and by strongly related graphs.

We obtain sharp upper bounds: if G is not a 4‐clique, then.

magnified image

The triangle cover number tmin(G) is also bounded above by Γ(G) = m ‐ n + c, the cyclomatic number of a graph G of order n with m edges and c connected components. Here we give a combinatorial proof for tmin(G) ⩽ Γ(G) and characterize the family of all extremal graphs satisfying equality.
Decompositions of graphs into trees
Authors: Lonc Zbigniew
Published: May 2007

Let θ be a family of graphs. By a θ‐decomposition of a graph G we mean a partition λ of the edge set of G such that every F ϵ π spans in G a subgraph isomorphic to a graph in θ.

In this paper we state the following conjecture: If T1 and T2 are two trees having relatively prime sizes then there exists c = c(T1 T2) such that every graph G satisfying the condition δ(G) ⩾ c has a {T1, T2}‐decom‐position. We prove this conjecture for some special pairs of trees. In particular, we prove it in the following cases:

(i) T1 and T2 are stars having relatively prime sizes;

(ii) T1 and T2 are paths having relatively prime sizes; and.

(iii) T1 = T2 ‐ {v}, where v is a terminal vertex in T2.
Some new perfect one‐factorizations from starters in finite fields
Authors: Dinitz J. H. , Stinson D. R.
Published: May 2007

We construct seven new examples of perfect one‐factorizations, in the complete graphs K126, K170, K730, K1370, K1850, K2198, and K3126. These are generated by two‐ and four‐quotient starters in finite fields. We also find several examples of perfect one‐factorizations that are not isomorphic to previously known examples.
On the construction of odd cycle systems
Authors: Hoffman D. G. , Lindner C. C. , Rodger C. A.
Published: May 2007

Three obvious necessary conditions for the existence of a k‐cycle system of order n are that if n > 1 then n ⩾ k, n is odd, and 2k divides n(n − 1). We show that if these necessary conditions are sufficient for all n satisfying k ⩽ n < 3k then they are sufficient for all n. In particular, there exists a 15‐cycle system of order n if and only if n ≡ 1, 15, 21, or 25 (mod 30), and there exists a 21‐cycle system of order n if and only if n ≡ 1, 7, 15, or 21 (mod 42), n ≠ 7. 15.
Path graphs
Authors: Broersma H. J. , Hoede C.
Published: May 2007

The concept of a line graph is generalized to that of a path graph. The path graph Pk(G) of a graph G is obtained by representing the paths Pk in G by vertices and joining two vertices whenever the corresponding paths Pk in G form a path Pk+1 or a cycle Ck. P3‐graphs are characterized and investigated on isomorphism and traversability. Trees and unicyclic graphs with hamiltonian P3‐graphs are characterized.
Some classes of perfectly orderable graphs
Authors: Hoàng C. T. , Reed B. A.
Published: May 2007

In 1981, Chvátal defined the class of perfectly orderable graphs. This class of perfect graphs contains the comparability graphs and the triangulated graphs. In this paper, we introduce four classes of perfectly orderable graphs, including natural generalizations of the comparability and triangulated graphs. We provide recognition algorithms for these four classes. We also discuss how to solve the clique, clique cover, coloring, and stable set problems for these classes.
Circumference and girth
Authors: Zhang Cun‐Quan
Published: May 2007

Let G be 2‐connected graph with girth g and minimum degree d. Then each pair of vertices of G is joined by a path of length at least max{1/2(d − 1)g, (d − 3/2)(g − 4) + 2} if g ⩾ 4, and the length of a longest cycle of G is at least max{[(d − 1)(g − 2) + 2], [(2d − 3)(g − 4) + 4]}.
A survey: Recent results, conjectures, and open problems in labeling graphs
Authors: Gallian Joseph A.
Published: May 2007

In this paper we organize and summarize much of the work done on graceful and harmonious labelings of graphs. Many open problems and conjectures are included.
Lower bounds on the number of triangles in a graph
Authors: Fisher David C.
Published: May 2007

For a simple graph G, let f(z) ≡ 1 − c1z + c3z2 − c3z3 + … where ck is the number of complete subgraphs on k nodes in G. Let r(G) be the reciprocal of the smallest real root of f(z). Let λ(Ḡ) be the spectral radius of the complement of G. We show r(G) ⩾ λ(Ḡ) + 1. This is used to show that if c21/4 ⩽ c2 ⩽ c21/3, then a lower bound on the number of triangles in G is c3 ⩾ [9c2c1 − 2c21 − 2(c21 − 3c2)3/2]/27. This improves a bound of Bollobás and is asymptotically sharp.

Also, this paper shows that magnified image (a corollary of a result from Erdös and Hanini) and the average number of triangles in a graph with c1 nodes and c2 edges is E(c3) = 3/4(C22 − 3c2 + 2)c2/(c31 − 5c1 − 4). These are graphically compared to the best known lower bounds.
A counterexample to the rank‐coloring conjecture
Authors: Alon N. , Seymour P. D.
Published: May 2007

It has been conjectured by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. We give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29.
Graphs with homeomorphically irreducible spanning trees
Authors: Albertson Michael O. , Berman David M. , Hutchinson Joan P. , Thomassen Carsten
Published: May 2007

It is an NP‐complete problem to decide whether a graph contains a spanning tree with no vertex of degree 2. We show that these homeomorphically irreducible spanning trees are contained in all graphs with minimum degree at least c√n and in triangulations of the plane. They are nearly present in all graphs of diameter 2. They do not necessarily occur in r‐regular or r‐connected graphs.
Perfect path double covers of graphs
Authors: Bondy J. A.
Published: May 2007

A perfect path double cover (PPDC) of a graph G on n vertices is a family 𝒫 of n paths of G such that each edge of G belongs to exactly two members of 𝒫 and each vertex of G occurs exactly twice as an end of a path of 𝒫. We propose and study the conjecture that every simple graph admits a PPDC. Among other things, we prove that every simple 3‐regular graph admits a PPDC consisting of paths of length three.
Arithmetic graphs
Authors: Acharya B. D. , Hegde S. M.
Published: May 2007

A (p, q)‐graph G is said to be (k, d)‐arithmetic if its vertices can be assigned distinct nonnegative integers so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices, can be arranged in the arithmetic progression k, k + d, k + 2d, …, k + (q ‐ 1)d. In this paper we initiate a study on the structures of finite (k, d)‐arithmetic graphs.
Embeddings of cartesian products of nearly bipartite graphs
Authors: Mohar Bojan , Pisanski Tomaž , White Arthur T.
Published: May 2007

Surgical techniques are often effective in constructing genus embeddings of cartesian products of bipartite graphs. In this paper we present a general construction that is “close” to a genus embedding for cartesian products, where each factor is “close” to being bipartite. In specializing this to repeated cartesian products of odd cycles, we are able to obtain asymptotic results in connection with the genus parameter for finite abelian groups.
Trees that admit 3‐to‐1 maps onto the circle
Authors: Heath Jo , Hilton A. J. W.
Published: May 2007

Trees that admit a continuous 3‐to‐1 map onto the circle are characterized.
More characterizations of triangulated graphs
Authors: Benzaken Claude , Crama Yves , Duchet Pierre , Hammer Peter L. , Maffray Frédéric
Published: May 2007

New characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability function has all its coefficients equal to 0, +1 or −1.
Induced subgraphs and well‐quasi‐ordering
Authors: Damaschke Peter
Published: May 2007

We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤i, and (2) well‐quasi‐ordered (WQO) by this relation. The main result shows that the class of cographs (P4‐free graphs) is WQO by ≤i, and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove that P4‐reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤i are also given.
On irredundant Ramsey numbers for graphs
Authors: Hattingh Johannes H.
Published: May 2007

The irredundant Ramsey number s(m, n) is the smallest p such that in every two‐coloring of the edges of Kp using colors red (R) and blue (B), either the blue graph contains an m‐element irredundant set or the red graph contains an n‐element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the form s(3, n) and prove that 18 ≤ s(3,7) ≤ 19.
Universal graphs and induced‐universal graphs
Authors: Chung Fan R. K.
Published: May 2007

We construct graphs that contain all bounded‐degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so‐called universal graphs (or induced‐universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced‐universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced‐universal graphs.
A characterization of graphs without long induced paths
Authors: Bacsó Gábor , Tuza Zsolt
Published: May 2007

In a connected graph define the k‐center as the set of vertices whose distance from any other vertex is at most k. We say that a vertex set S d‐dominates G if for every vertex x there is a y ∈ S whose distance from x is at most d.

Call a graph Pt‐free if it does not contain a path on t vertices as an induced subgraph. We prove that a connected graph is P2k‐1‐free (P2k‐free) if and only if each of its connected induced subgraphs H satisfy the following property: The k‐center of H (k ‐ 1)‐dominates ((k ‐ 2)‐dominates) H.

Moreover, we show that the subgraph induced by the (t ‐ 3)‐center in any Pt‐free connected graph is again connected and has diameter at most t ‐ 3.
Removable edges in 3‐connected graphs
Authors: Holton Derek A. , Jackson Bill , Saito Akira , Wormald Nicholas C.
Published: May 2007

An edge e of a 3‐connected graph G is said to be removable if G ‐ e is a subdivision of a 3‐connected graph. If e is not removable, then e is said to be nonremovable. In this paper, we study the distribution of removable edges in 3‐connected graphs and prove that a 3‐connected graph of order n ≥ 5 has at most [(4 n — 5)/3] nonremovable edges.
A note on the star chromatic number
Authors: Bondy J. A. , Hell Pavol
Published: May 2007

A. Vince introduced a natural generalization of graph coloring and proved some basic facts, revealing it to be a concept of interest. His work relies on continuous methods. In this note we make some simple observations that lead to a purely combinatorial treatment. Our methods yield shorter proofs and offer further insight.
One sufficient condition for hamiltonian graphs
Authors: Chen Guantao
Published: May 2007

Let G be a 2‐connected graph of order n. We show that if

for each pair of nonadjacent vertices x,y ∈ V(G), then G is Hamiltonian.
Trees with very few eigenvalues
Authors: Beezer Robert A.
Published: May 2007

The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance‐transitive and distance‐regular graphs. Here we provide a recursive construction that will create graphs having the fewest possible eigenvalues. This construction is best at creating trees, but will also create cyclic graphs meeting the lower bound. Unlike the graphs mentioned above, many of the graphs constructed do not exhibit large amounts of symmetry. A corollary allows us to determine the values and multiplicities of all the nonsimple eigenvalues of the constructed graph.
Size and independence in triangle‐free graphs with maximum degree three
Authors: Jones Kathryn Fraughnaugh
Published: May 2007

Let C be the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of C is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As corollaries, we obtain the best possible lower bound for the independence ratio of a graph in C and evaluate some Ramsey‐type numbers.
Minimum cycle coverings and integer flows
Authors: Zhang Cun‐Quan
Published: May 2007

It was conjectured by Fan that if a graph G = (V,E) has a nowhere‐zero 3‐flow, then G can be covered by two even subgraphs of total size at most |V| + |E| ‐ 3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the Chinese postman problem and the solution of minimum cycle covering problem are equivalent for any graph admitting a nowhere‐zero 4‐flow.
Extremal cover times for random walks on trees
Authors: Brightwell Graham , Winkler Peter
Published: May 2007

Let Cν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for Cν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that Cν(T) is minimized when T is a star and v is one of its leaves.

In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).
Which line‐graphs are perfectly orderable?
Authors: Chvátal V.
Published: May 2007

We characterize (by forbidden induced subgraphs) those line‐graphs that are perfectly orderable. Implicit in our presentation is a polynomial, time algorithm for recognizing these graphs.
Cataloging graphs by generating them uniformly at random
Authors: Kerber A. , Laue R. , Hager R. , Weber W.
Published: May 2007

We describe an algorithm for cataloging graphs by generating them uniformly at random. The method used is based on a recent algorithm by Dixon and Wilf that generates orbit representatives uniformly at random. The approach is refined to graphs with prescribed numbers of edges and vertices, and then applied to obtain the complete list of graphs on 10 vertices.
Extending an edge‐coloring
Authors: Marcotte O. , Seymour P. D.
Published: May 2007

When can a k‐edge‐coloring of a subgraph K of a graph G be extended to a k‐edge‐coloring of G? One necessary condition is that

for all X ⊆ E(G) ‐ E(K), where μi(X) is the maximum cardinality of a subset of X whose union with the set of edges of K colored i is a matching. This condition is not sufficient in general, but is sufficient for graphs of very simple structure. We try to locate the border where sufficiency ends.
Coloring the edges of km × km
Authors: Heinrich Katherine
Published: May 2007

In the graph Km × Km a 4‐cycle is called square if its vertices do not all lie in the same copy of Km. A c‐coloring of the edges of Km × Km is good if in any square 4‐cycle the two edges of at least one nonadjacent pair receive different colors. Let f(2,c) denote the smallest integer m so that no c‐coloring of Km × Km is good. We show that there exists a constant k so that f(2,c) > kc3. (This function was introduced by Shelah in his proof of van der Waerden's theorem).
Extremal subgraphs of random graphs
Authors: Babai László , Simonovits Miklós , Spencer Joel
Published: May 2007

We 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

We 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

Let 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

An 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

We 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

Let 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.
Hamiltonian tournaments with the least number of 3‐cycles
Authors: Burzio M. , Demaria D. C.
Published: May 2007

We characterize the family of hamiltonian tournaments with the least number of 3‐cycles, studying their structure and their score sequence. Furthermore, we obtain the number of nonisomorphic tournaments of this family.
Balanced graphs with edge density constraints
Authors: Sheehan John
Published: May 2007

Suppose 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

For 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.
Diagonal 11‐coloring of plane triangulations
Authors: Borodin Oleg V.
Published: May 2007

The vertices of each plane triangulation without loops and multiple edges may be colored with 11 colors so that for every two adjacent triangles [xyz] and [wxy], the vertices x,y,w,z are colored pairwise differently.
Trees and unicyclic graphs with hamiltonian path graphs
Authors: Yu Xingxing
Published: May 2007

We prove two conjectures of Broersma and Hoede about path graphs of trees and unicyclic graphs.
The star chromatic number of a graph
Authors: Abbott H. L. , Zhou B.
Published: May 2007

We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.
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

It 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

For 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

In 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

For (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

It 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.
The solution to an extremal problem on balanced extensions of graphs
Authors: Ruciński A. , Vince A.
Published: May 2007

For n sufficiently large the order of a smallest balanced extension of a graph of order n is, in the worst case, ⌊(n + 3)2/8⌋. © 1993 John Wiley & Sons, Inc.
On the greedoid polynomial for rooted graphs and rooted digraphs
Authors: McMahon Elizabeth W.
Published: May 2007

We 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

Jo 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.
On the characterization of path graphs
Authors: Li Huaien , Lin Yixun
Published: May 2007

Broersma and Hoede have introduced path graphs. Their characterization of P3‐graphs contains a flaw. This note presents the correct form of the characterization. © 1993 John Wiley & Sons, Inc.
Almost all trees share a complete set of immanantal polynomials
Authors: Botti Phillip , Merris Russell
Published: May 2007

Let χ 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.