Graph minors and linkages

Bollobás and Thomason showed that every 22k‐connected graph is k‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7n?29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005     

The determining number of a Cartesian product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q_n)=?log₂n?+1 which matches the lower bound, and that Det(K)=?log₃(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hⁿ)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory     

Subgraphs smaller than the girth

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.     

Acyclic edge chromatic number of outerplanar graphs

A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010     

On the minimum size of tight hypergraphs

A k-graph, H = (V, E), is tight if for every surjective mapping f: V → {1,….k} there exists an edge α ? E sicj tjat f|_α is injective. Clearly, 2-graphs are tight if and only if they are connected. Bounds for the minimum number ? of edges in a tight k-graph with n vertices are given. We conjecture that ? for every n and prove the equality when 2n + 1 is prime. From the examples, minimal embeddings of complete graphs into surfaces follow. © 1992 John Wiley & Sons, Inc.     

Two‐sided Group Digraphs and Graphs

We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets of a group G, we define the two‐sided group digraph to have vertex set G, and an arc from x to y if and only if for some and . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which may be viewed as a simple graph of valency , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.     

On Ramsey‐type positional games

Let K denote the graph obtained from the complete graph K_s+t by deleting the edges of some K_t‐subgraph. We prove that for each fixed s and sufficiently large t, every graph with chromatic number s+t has a K minor. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 343–350, 2010     

Enumeration of graphs by degree sequence

The degree sequence (d₀, d₁, …, d_p-1) of a graph G of order p is defined by d_k = the number of points of G of degree k. Methods of Robinson are extended to produce a generating function F(x₀, x₁, x₂, …) where the coefficient of x…x is the number of graphs of order p having degree sequence (d₀, …, d_p-1).     

Finite fields and the 1‐chromatic number of orientable surfaces

The 1‐chromatic number χ₁(S_p) of the orientable surface S_p of genus p is the maximum chromatic number of all graphs which can be drawn on the surface so that each edge is crossed by no more than one other edge. We show that if there exists a finite field of order 4m+1, m≥3, then 8m+2≤χ₁(S)≤8m+3, where 8m+3 is Ringel's upper bound on χ₁(S). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 179–184, 2010     

A generalization of Plantholt's theorem

Let K denote the complete graph K_2n+1 with each edge replicated r times and let χ′(G) denote the chromatic index of a multigraph G. A multigraph G is critical if χ′(G) > χ′(G/e) for each edge e of G. Let S be a set of sn – 1 edges of K. We show that, for 0 < s ≦ r, G/S is critical and that χ′ (G/(S ∪{e})) = 2rn + r – s for all e ∈ E(G/S). Plantholt [M. Plantholt, The chromatic index of graphs with a spanning star. J. Graph Theory 5 (1981) 5–13] proved this result in the case when r = 1.     

On a conjecture on maximal planar sequences

Let d1 d2 dp denote the nonincreasing sequence d₁, …, d₁, d₂, …, d₂, …, d_p, …, d_p, where the term d_i appears k_i times (i = 1, 2, …, p). In this work the author proves that the maximal 2-sequences: 7³6¹5¹⁵, 7⁵6¹5¹⁷, 7⁷6¹5¹⁹ are planar graphical, in contrast to a conjecture by Schmeichel and Hakimi.     

Intersections of graphs

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H. We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K₂ with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P, the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011     

Cayley Graphs of Diameter Two from Difference Sets

Let and be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree d and diameter k. When , it is well known that with equality if and only if the graph is a Moore graph. In the abelian case, we have . The best currently lower bound on is for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that for sufficiently large d and if , and m is odd.     

Some results on cyclic interval edge colorings of graphs

A proper edge coloring of a graph G with colors is called a cyclic interval t‐coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree admits a cyclic interval ‐coloring if for every vertex v the degree satisfies either or . We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for ‐biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)‐biregular graphs as well as all ‐biregular () graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.     

Short cycle covers of graphs and nowhere‐zero flows

A shortest cycle cover of a graph G is a family of cycles which together cover all the edges of G and the sum of their lengths is minimum. In this article we present upper bounds to the length of shortest cycle covers, associated with the existence of two types of nowhere‐zero flows—circular flows and Fano flows. Fano flows, or Fano colorings, are nowhere‐zero ?‐flows on cubic graphs, with certain restrictions on the flow values meeting at a vertex. Such flows are conjectured to exist on every bridgless cubic graph. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 68:340‐348, 2011     

Recursive constructions for triangulations

Three recursive constructions are presented; two deal with embeddings of complete graphs and one with embeddings of complete tripartite graphs. All three facilitate the construction of 2) non‐isomorphic face 2‐colourable triangulations of K_n and K_n,n,n in orientable and non‐orientable surfaces for values of n lying in certain residue classes and for appropriate constants a. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 87–107, 2002     

Biembeddings of Abelian groups

We prove that, with the single exception of the 2‐group C, the Cayley table of each Abelian group appears in a face 2‐colorable triangular embedding of a complete regular tripartite graph in an orientable surface. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 71–83, 2010     

Isomorphism criterion for monomial graphs

Let q be a prime power, ??_q be the field of q elements, and k, m be positive integers. A bipartite graph G = G_q(k, m) is defined as follows. The vertex set of G is a union of two copies P and L of two‐dimensional vector spaces over ??_q, with two vertices (p₁, p₂) ∈ P and [ l₁, l₂] ∈ L being adjacent if and only if p₂ + l₂ = pl. We prove that graphs G_q(k, m) and G_q′(k′, m′) are isomorphic if and only if q = q′ and {gcd (k, q ? 1), gcd (m, q ? 1)} = {gcd (k′, q ? 1),gcd (m′, q ? 1)} as multisets. The proof is based on counting the number of complete bipartite INFgraphs in the graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 322–328, 2005     

The size of strength-maximal graphs

Let G be a graph and let k′(G) be the edge-connectivity of G. The strength of G, denoted by k?′(G), is the maximum value of k′(H), where H runs over all subgraphs of G. A simple graph G is called k-maximal if k?′(G) ≤ k but for any edge e ∈ E(G^c), k?′(G + e) ≥ k + 1. Let G be a k-maximal graph of order n. In [3], Mader proved |E(G)| ≤ (n - k)k + (). In this note, we shall show (n - 1)k - () In?n/k + 2)? ≤ |E(G|, and characterize the extremal graphs. We shall also give a characterization of all k-maximal graphs.     

On Rooted Packings,Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted ‐packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ‐packings in this case.