Generalized Rotation numbers

A rooted graph is a pair (G,x), where G is a simple undirected graph and x ∈ V(G). If G is rooted at x, its kth rotation number h_k (G,x) is the minimum number of edges in a graph F of order |G| + k such that for every v ∈ V(F) we can find a copy of G in F with the root vertex x at v. When k = 0, this definition reduces to that of the rotation number h(G,x), which was introduced in [“On Rotation Numbers for Complete Bipartite Graphs,” University of Victoria, Department of Mathematics Report No. DM-186-IR (1979)] by E.J. Cockayne and P.J. Lorimer and subsequently calculated for complete multipartite graphs. In this paper, we estimate the kth rotation number for complete bipartite graphs G with root x in the larger vertex class, thereby generalizing results of B. Bollobás and E.J. Cockayne [“More Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory, Vol. 6 (1982), pp. 403–411], J. Haviland [“Cliques and Independent Sets,” Ph. D. thesis, University of Cambridge (1989)], and J. Haviland and A. Thomason [“Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory, Vol. 16 (1992), pp. 61–71]. © 1993 John Wiley & Sons, Inc.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

Prime graphs and exponential composition of species

In this paper, we enumerate prime graphs with respect to the Cartesian multiplication of graphs. We use the unique factorization of a connected graph into the product of prime graphs given by Sabidussi to find explicit formulas for labeled and unlabeled prime graphs. In the case of species, we construct the exponential composition of species based on the arithmetic product of species of Maia and Méndez, and express the species of connected graphs as the exponential composition of the species of prime graphs.     

Closures,cycles, and paths

In 1960 Ore proved the following theorem: Let G be a graph of order n. If d(u) + d(v)≥n for every pair of nonadjacent vertices u and v, then G is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have been obtained, so‐called “Ore‐type degree conditions”. In [R. J. Faudree, R. H. Schelp, A. Saito, and I. Schiermeyer, Discrete Math 307 (2007), 873–877], Faudree et al. strengthened Ore's theorem as follows: They determined the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore's condition) but still imply that the graph is hamiltonian. In this article we prove that for some other graph properties the corresponding Ore‐type degree conditions can be strengthened as well. These graph properties include traceable graphs, hamiltonian‐connected graphs, k‐leaf‐connected graphs, pancyclic graphs, and graphs having a 2‐factor with two components. Graph closures are computed to show these results. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 314–323, 2012     

A polynomial time algorithm recognizing link trees

The link of a vertex v of a graph G is the subgraph induced by all vertices adjacent to v. If all the links of G are isomorphic to a finite graph L, then G is called a realization of L, and L is called a link graph. At the Smolenice symposium of 1963, Zykov posed the problem of recognizing link graphs. There are two versions of that problem, namely the finite (the existence of a finite realization is required) and the infinite one. Bulitko (see “On Graphs with Prescribed Links of Vertices” [in Russian], Trudy mat. inst. im. Steklova, Vol. 133, 1973, pp. 78-94) proved that the infinite version is algorithmically unsolvable. The solution of both versions is known only for special classes of graphs as paths, cycles, and graphs homeomorphic to a star (see M. Brown and R. Connelly, “On Graphs with a Constant Link I,” New Directions in the Theory of Graphs, Academic Press, New York, 1973, pp. 19-51; On Graphs with a Constant Link II, Discrete Mathematics, Vol. 11, 1975, pp. 199-232). The finite version for trees with less than 10 vertices has been solved by Blass, Harary, and Miller (see “Which Trees Are Link Graphs?” Journal of Combinatorics Theory Series B, Vol. 29, 1980, pp. 277-292). Trees that are link graphs are called link trees. Using some previous results of Bulitko (see “On a Recursive Property of Block-Complete Graphs” [in Russian], Proceedings of Czechoslovak Conference on Graphs, Zemplínska ?irava, 1978, p. 20-30), we present a polynomial time algorithm recognizing link trees. The applied methods have some remarkable consequences concerning the study of link graphs. © 1995 John Wiley & Sons, Inc.     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

Minimally (k,k)‐edge‐connected graphs

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K₂, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

Game coloring the Cartesian product of graphs

This article proves the following result: Let G and G′ be graphs of orders n and n′, respectively. Let G^* be obtained from G by adding to each vertex a set of n′ degree 1 neighbors. If G^* has game coloring number m and G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k + m ? 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

A characterization of weakly four‐connected graphs

A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G ? x is 2‐edge‐connected for all x ∈ V. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006     

Generalized steinhaus graphs

A generalized Steinhaus graph of order n and type s is a graph with n vertices whose adjacency matrix (a_i,j) satisfies the relation where 2 ≦i≦n?1, i + s(i ? 1 ≦ j ≦ n, c_r,i,j ? {0,1} for all 0 ≦ r ≦ s(i) ?1 and c_s(i)?1,i,j = 1. The values of s(i) and c_r,i,j are fixed but arbitrary. Generalized Steinhaus graphs in which each edge has probability ½ are considered. In an article by A. Blass and F. Harary [“Properties of Almost All Graphs and Complexes,” Journal of Graph Theory, Vol. 3 (1976), pp. 225–240], a collection of first-order axioms are given from which any first-order property in graph theory or its negation can be deduced. We show that almost all generalized Steinhaus graphs satisfy these axioms. Thus the first-order theory of random generalized Steinhaus graphs is identical with the theory of random graphs. Quasi-random properties of graphs are described by F. R. K. Chung, R. L. Graham, and R. M. Wilson, [“Quasi-Random Graphs,” Combinatorica, Vol. 9 (1989), pp. 345–362]. We conclude by demonstrating that almost all generalized Steinhaus graphs obey Property 2 and hence all equivalent quasi-random properties. © 1996 John Wiley & Sons, Inc.     

Excluding Induced Subdivisions of the Bull and Related Graphs

For any graph H, let Forb*(H) be the class of graphs with no induced subdivision of H. It was conjectured in [J Graph Theory, 24 (1997), 297–311] that, for every graph H, there is a function f_H: ?→? such that for every graph G∈Forb*(H), χ(G)≤f_H(ω(G)). We prove this conjecture for several graphs H, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex‐disjoint pendant edges), and what we call a “necklace,” that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:49–68, 2012     

Graphs with given group and given constant link

A 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 ? Γ.     

Det‐extremal cubic bipartite graphs

Let G be a connected k–regular bipartite graph with bipartition V(G) = X ∪ Y and adjacency matrix A. We say G is det‐extremal if per (A) = |det(A)|. Det–extremal k–regular bipartite graphs exist only for k = 2 or 3. McCuaig has characterized the det‐extremal 3‐connected cubic bipartite graphs. We extend McCuaig's result by determining the structure of det‐extremal cubic bipartite graphs of connectivity two. We use our results to determine which numbers can occur as orders of det‐extremal connected cubic bipartite graphs, thus solving a problem due to H. Gropp. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 50–64, 2003     

Chromaticity of triangulated graphs

It is shown here that a connected graph G without subgraphs isomorphic to K₄ is triangulated if and only if its chromatic polynomial P(G,λ) equals λ(λ ? 1)^m(λ ? 2)^r for some integers m ≧ 1, r ≧ 0. This result generalizes the characterization of Two-Trees given by E.G. Whitehead [“Chromaticity of Two-Trees,” Journal of Graph Theory 9 (1985) 279–284].     

On the X-join decomposition for undirected graphs

In his paper [17], Sabidussi defined the X-join of a family of graphs. Cowan, James, Stanton gave in [6] and O(n⁴) algorithm that decomposes a graph, when possible, into the X-join of the family of its subgraphs. We give here another approach using an equivalence relation on the edge set of the graph. We prove that if G and its complement are connected then there exists an unique class of edges that covers all the vertices of G. This theorem yields immediately an O(n³) decomposition algorithm.