bluuebunny/crossref_metadata_2025_split huggingface dataset:
A note on constructive methods for ramsey numbers
Authors: Chung F. R. K. 
Published: May 2007

AbstractLet r(k) denote the least integer n‐such that for any graph G on n vertices either G or its complement G contains a complete graph Kk on k vertices. in this paper, we prove the following lower bound for the Ramsey number r(k) by explicit construction: r(k) ≥ exp (c(Log k)4/3[(log log k)1/3] for some constant c> 0.
On the reconstruction of locally finite trees
Authors: Andreae Thomas 
Published: May 2007

AbstractWe prove a theorem saying, when taken together with previous results of Bondy, Hemminger, and Thomassen, that every locally finite, infinite tree not containing a subdivision of the dyadic tree (i. e., the regular tree of degree 3) is uniquely determined, up to isomorphism, from its collection of vertex‐deleted subgraphs. Furthermore, as another partial result concerning the reconstruction of locally finite trees, we show that the same is true for locally finite trees whose set of vertices of degree s is nonempty and finite (for some positive integer s).
A construction of chromatic index critical graphs
Authors: Yap Hian Poh 
Published: May 2007

AbstractWe prove that if K is an undirected, simple, connected graph of even order which is of class one, regular of degree p ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph G obtained from K by splitting any vertex is p‐critical. We find that various constructions of critical graphs by S. Fiorini are special cases of a corollary of this result.
Hamiltonian groups are color‐graph‐hamiltonian
Authors: Klerlein Joseph B. , Starling A. Gregory 
Published: May 2007

AbstractA group Γ is said to be color ‐graph ‐hamiltonian if Γ has a minimal generating set Δ such that the Cayley color graph DΔ(Γ) is hamiltonian. It is shown that every hamiltonian group is color ‐graph ‐hamiltonian.
An extremal problem for paths in bipartite graphs
Authors: Gyárfás A. , Rousseau C. C. , Schelp R. H. 
Published: May 2007

AbstractA formula is found for the maximum number of edges in a graph G ⊆ K(a, b) which contains no path P2l for l > c. A similar formula is found for the maximum number of edges in G ⊆ K(a, b) containing no P2l + 1 for l > c. In addition, all extremal graphs are determined.
Graphs with given group and given constant link
Authors: Vogler Walter 
Published: May 2007

AbstractA graph L is called a link graph if there is a graph G such that for each vertex of G its neighbors induce a subgraph isomorphic to L. Such a G is said to have constant link .L Sabidussi proved that for any finite group F and any n ⩾ 3 there are infinitely many n‐regular connected graphs G with AutG ≅ Γ. We will prove a stronger result: For any finite group Γ and any link graph L with at least one isolated vertex and at least three vertices there are infinitely many connected graphs G with constant link L and AutG ≅ Γ.
Edge‐coloring of multigraphs: Recoloring technique
Authors: Goldberg Mark K. 
Published: May 2007

AbstractNew upper and lower bounds for the chromatic index of a finite muitigraph are obtained. A complete description is given of multigraphs satisfying χ′ > 1/8(9ρ + 6) where χ′ and ρ denote the chromatic index and the maximum vertex degree of a multigraph. Some new and old conjectures are discussed.
Hamiltonian results in K1,3‐free graphs
Authors: Matthews M. M. , Sumner D. P. 
Published: May 2007

AbstractThere have been a number of results dealing with Hamiltonian properties in powers of graphs. In this paper we show that the square and the total graph of a K1,3‐free graph are vertex pancyclic. We then discuss some of the relationships between connectivity and Hamiltonian properties in K1,3‐free graphs.
Forbidden subgraphs and hamiitonian properties in the square of a connected graph
Authors: Gould Ronald J. , Jacobson Michael S. 
Published: May 2007

AbstractVarious Harniltonian‐like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K1,4 the subdivision graph of K1,3, and the subdivision graph of K1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the subdivision graph of K1,3 minus an endvertex have vertex pancyclic squares.
Minimum K‐hamiltonian graphs
Authors: Wong W. W. , Wong C. K. 
Published: May 2007

AbstractWe consider two new classes of graphs arising from reliability considerations in network design. We want to construct graphs with a minimum number of edges which remain Hamiltonian after k edges (or k vertices) have been removed. A simple construction is presented for the case when k is even. We show that it is minimum k‐edge Hamiltonian. On the other hand, Chartrand and Kapoor previously proved that this class of graphs was also minimum k‐vertex Hamiltonian. The case when k is large (odd or even) is also considered. Some results about directed graphs are also presented.
On the number of vertices of given degree in a random graph
Authors: Palka Zbigniew 
Published: May 2007

AbstractThis note can be treated as a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G ∈ 𝒢(n, p) asymptotically has a normal distribution.
The linear arboricity of some regular graphs
Authors: Enomoto Hikoe , Péroche Bernard 
Published: May 2007

AbstractWe prove that the linear arboricity of every 5‐regular graph is 3. That is, the edges of any 5‐regular graph are covered by three linear forests. We also determine the linear arboricity of 6‐regular graphs and 8‐regular graphs. These results improve the known upper bounds for the linear arboricity of graphs with given maximum degree.
On a problem of a. kotzig concerning factorizations of 4‐regular graphs
Authors: Zelinka Bohdan 
Published: May 2007

AbstractThe paper gives a solution of a problem of A. Kotzǐg. This problem concerns the 4‐regular graphs G with the property that in every decomposition of G into two edge‐disjoint 2‐regular factors at least one factor is a Hamiltonian circuit in G.
Box‐threshold graphs
Authors: Peled Uri N. , Simeone Bruno 
Published: May 2007

AbstractA graph is called box‐threshold when all pairs of vertices with incomparable neighborhoods have the same degree. Several properties of box‐threshold graphs, generalizing properties of threshold graphs, are proved. A transportation model with priority constraints is used to characterize their degree sequences. Further characterizations are given using the concept of the frame of a graph.
Connected, locally 2‐connected, K1,3‐free graphs are panconnected
Authors: Kanetkar S. V. , Rao P. R. 
Published: May 2007

AbstractA graph G is locally n‐connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n‐connected. We prove that every connected, locally 2‐connected graph containing no induced subgraph isomorphic to K1,3 is panconnected.
The cycle space of an embedded graph
Authors: Richter B. , Shank H. 
Published: May 2007

AbstractLet G be a connected graph with edge set E embedded in the surface ∑. Let G° denote the geometric dual of G. For a subset d of E, let τd denote the edges of G° that are dual to those edges of G in d. We prove the following generalizations of well‐known facts about graphs embedded in the plane.(1) b is a boundary cycle in G if and only if τb is a cocycle in G°.(2) If T is a spanning tree of G, then τ(E/T) contains a spanning tree of G°.(3) Let T be any spanning tree of G and, for e ϵ	E/T, let T(e) denote the fundamental cycle of e. Let U ∪ E/T. Then τU is a spanning tree of G° if and only if the set of face boundaries, less any one, together with the set {T(e); e ϵ E/(T ∪ U)} is a basis for the cycle space of G.
Cutpoints and the chromatic polynomial
Authors: Whitehead Earl Glen , Zhao Lian‐Chang 
Published: May 2007

AbstractWe prove that the multiplicity of the root 1 in the chromatic polynomial of a simple graph G is equal to the number of nontrivial blocks in G. In particular, a connected simple graph G has a cutpoint if and only if its chromatic polynomial is divisible by (λ – 1)2. We apply this theorem to obtain some chromatic equivalence and uniqueness results.
Doubly eulerian trails on rectangular grids
Authors: Brenner J. L. , Lyndon R. C. 
Published: May 2007

AbstractLet K be the 1‐skeleton of the regular tessellation of Euclidean n‐space by n‐cubes, n ≥ 2. We show that K admits a doubly Eulerian trail (simply Eulerian trail), that is, a doubly infinite path π = … e−1e0e1 … where, out of each pair {e, e−1} of oppositely directed edges, both (exactly one) appear(s) exactly once in π, and where no ei+1 = ei−1 (there are no U‐turns).
On the reconstruction of rayless infinite forests
Authors: Andreae Thomas , Schmidt Rüdiger 
Published: May 2007

AbstractA graph G is called strongly p‐reconstructible if it is (up to isomorphism) uniquely determined by the collection of its pairwise nonisomorphic subgraphs G – v where v is a pendent vertex of G. Using previous results of the second author concerning the structure of infinite rayless graphs it is shown that every rayless forest with an infinite edge‐set is strongly p‐reconstructible. This result is applied to the classical reconstruction problem to find that every infinite rayless forest G with a finite number of components is reconstructible; i.e., G is (up to isomorphism) uniquely determined by its collection of vertex‐deleted subgraphs. Furthermore, an example is given which shows that nonreconstructible rayless forests with a countable number of components exist.
Note on the existence of directed (k + 1)‐cycles in diconnected complete k‐partite digraphs
Authors: Balakrishnan R. , Paulraja P. 
Published: May 2007

AbstractA graph is constructed to provide a negative answer to the following question of Bondy: Does every diconnected orientation of a complete k‐partite (k ≥ 5) graph with each part of size at least 2 yield a directed (k + 1)‐cycle?
On the distribution of cycle lengths in graphs
Authors: Gyárfás A. , Komlós J. , Szemerédi E. 
Published: May 2007

AbstractThe set of different cycle lengths of a graph G is denoted by C(G). We study how the distribution of C(G) depends on the minimum degree of G. We prove two results indicating that C(G) is dense in some sense. These results lead to the solution of a conjecture of Erdös and Hajnal stating that for suitable positive constants a, b the following holds: magnified image where δ(G) denotes the minimum degree of G.
The chromatic index of graphs of even order with many edges
Authors: Chetwynd A. G. , Hilton A. J. W. 
Published: May 2007

AbstractWe show that, for r = 1, 2, a graph G with 2n + 2 (≥6) vertices and maximum degree 2n + 1 ‐ r is of Class 2 if and only if |E(G/v)| > () ‐ rn, where v is a vertex of G of minimum degree, and we make a conjecture for 1 ≤ r ≤ n, of which this result is a special case. For r = 1 this result is due to Plantholt.
Circulants and their connectivities
Authors: Boesch F. , Tindell R. 
Published: May 2007

AbstractThere is diverse literature on various properties of a class of graphs known as circulants. We present a new result which answers the previously unsolved question of characterizing the connection sequence of circulants having point connectivity equal to point degree. We also develop some theorems regarding a new generalization of connectivity known as super‐connectivity. In addition, we give a survey of published results pertinent to the study of connectivity of circulants.
Retracts of hypercubes
Authors: Bandelt H. J. 
Published: May 2007

AbstractAn induced subgraph G of a graph H is a retract of H if there is an edge‐preserving map f from H onto G such that f|G is the identity map on G. A median graph is a connected graph such that for any three vertices u,v and w, there exists a unique vertex x which lies simultaneously on some shortest (u,v)‐, (v,w)‐, and (w,u)‐paths. It is shown that a graph G is a retract of some hypercube if and only if G is a median graph.
Diameter bounds for altered graphs
Authors: Chung F. R. K. , Garey M. R. 
Published: May 2007

AbstractThe main question addressed in this article is the following: If t edges are removed from a (t + 1) edge‐connected graph G having diameter D, how large can the diameter of the resulting graph be? (The diameter of a graph is the maximum, over all pairs of vertices, of the length of the shortest path joining those vertices.) We provide bounds on this value that imply that the maximum possible diameter of the resulting graph, for large D and fixed t, is essentially (t + 1) · D. The bulk of the proof consists of showing that, if t edges are added to an n‐vertex path Pn, then the diameter of the resulting graph is at least (n/(t + 1)) ‐ 1. Using a similar proof, we also show that if t edges are added to an n‐vertex cycle Cn, then the least possible diameter of the resulting graph is (for large n) essentially n/(t + 2) when t is even and n/(t + 1) when t is odd. Examples are given in all these cases to show that there exist graphs for which the bounds are achieved. We also give results for the corresponding vertex deletion problem for general graphs. Such results are of interest, for example, when studying the potential effects of node or link failures on the performance of a communication network, especially for networks in which the maximum time‐delay or signal degradation is directly related to the diameter of the network.
An upper bound for the k‐domination number of a graph
Authors: Cockayne E. J. , Gamble B. , Shepherd B. 
Published: May 2007

AbstractThe k‐domination number of a graph G, γk(G), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k, then γk(G) ≤ kp/(k + 1).
The square of a connected S(K1,3)‐free graph is vertex pancyclic
Authors: Hendry George , Vogler Walter 
Published: May 2007

AbstractWe prove the conjecture of Gould and Jacobson that a connected S(K1,3)‐free graph has a vertex pancyclic square. Since S(K1,3)2 is not vertex pan‐cyclic, this result is best possible.
Cataloguing the graphs on 10 vertices
Authors: Cameron R. D. , Colbourn C. J. , Read R. C. , Wormald N. C. 
Published: May 2007

AbstractWe describe the production of a catalogue of all the nonisomorphic graphs on 10 vertices by means of a computer program. The basic program generated all the nonisomorphic graphs with a given degree sequence. Some tables, derived from the catalogue, concerning the numbers of automorphisms of these graphs are given at the end of the paper.
The longest cycle of a graph with a large minimal degree
Authors: Alon Noga 
Published: May 2007

AbstractWe 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

AbstractWe 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

AbstractBounds 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.
Existence of graphs with prescribed mean distance
Authors: Hendry G. R. T. 
Published: May 2007

AbstractIt 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:
Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs
Authors: Pritikin Dan 
Published: May 2007

AbstractGraham 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

AbstractLet 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).
Some large graphs with given degree and diameter
Authors: Alegre I. , Fiol M. A. , Yebra J. L. A. 
Published: May 2007

AbstractThis 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

AbstractA 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

AbstractThe 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 exposition
Authors: Lesniak Linda , Oellermann Ortrud R. 
Published: May 2007

AbstractAn 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

AbstractA 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.
The nonorientable genus is additive
Authors: Archdeacon Dan 
Published: May 2007

AbstractA 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

AbstractA 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.
Longest cycles in 3‐connected graphs contain three contractible edges
Authors: Dean Nathaniel , Hemminger Robert L. , Ota Katsuhiro 
Published: May 2007

AbstractWe 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

AbstractA 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

AbstractWe 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.