bluuebunny/crossref_metadata_2025_split huggingface dataset:
On the genus of the semidirect product of ℤ9 by ℤ3
Authors: Brin Matthew G. , Rauschenberg David E. , Squier Craig C. 
Published: May 2007

AbstractWe 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

AbstractWe 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).
Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs
Authors: Kjær Jørgensen Leif 
Published: May 2007

AbstractA 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.
Graph spanners
Authors: Peleg David , Schäffer Alejandro A. 
Published: May 2007

AbstractGiven 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

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

AbstractA 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

AbstractThe 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.
A decomposition for strongly perfect graphs
Authors: Olariu Stephan 
Published: May 2007

AbstractA 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

AbstractOre 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

AbstractThe 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

AbstractWe 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

AbstractWe 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

AbstractSuppose 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 imageThe 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

AbstractLet θ 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

AbstractWe 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

AbstractThree 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

AbstractThe 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

AbstractIn 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

AbstractLet 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]}.
Lower bounds on the number of triangles in a graph
Authors: Fisher David C. 
Published: May 2007

AbstractFor 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

AbstractIt 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

AbstractIt 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

AbstractA 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

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

AbstractSurgical 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.
More characterizations of triangulated graphs
Authors: Benzaken Claude , Crama Yves , Duchet Pierre , Hammer Peter L. , Maffray Frédéric 
Published: May 2007

AbstractNew 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

AbstractWe 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

AbstractThe 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

AbstractWe 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

AbstractIn 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

AbstractAn 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.
Trees with very few eigenvalues
Authors: Beezer Robert A. 
Published: May 2007

AbstractThe 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

AbstractLet 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

AbstractIt 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

AbstractLet 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).
Cataloging graphs by generating them uniformly at random
Authors: Kerber A. , Laue R. , Hager R. , Weber W. 
Published: May 2007

AbstractWe 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

AbstractWhen 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

AbstractIn 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).