Decompositions of Km,n into cubes

For a complete bipartite graph to be decomposable into isomorphic cubes, certain conditions on the number of cube and bipartition vertices must hold. We prove these necessary conditions sufficient in some cases. For cubes of fixed dimension d (indeed for d-regular bipartite graphs in general) we show that proving sufficiency can be reduced to decomposing a finite number of complete bipartite graphs. When t = 2^d−1 and r is the remainder on dividing t by d, we show K_t,t is decomposable into d-cubes and an r-factor, where if r > 0 this r-factor itself is decomposable into r-cubes. © 1996 John Wiley & Sons, Inc.     

Almost all regular graphs are hamiltonian

In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r-regular graphs are hamiltonian for any fixed r ? 3, by an analysis of the distribution of 1-factors in random regular graphs. Moreover, almost all such graphs are r-edge-colorable if they have an even number of vertices. Similarly, almost all r-regular bipartite graphs are hamiltonian and r-edge-colorable for fixed r ? 3. © 1994 John Wiley & Sons, Inc.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Large regular graphs with no induced 2K 2

Letr be a positive integer. Considerr-regular graphs in which no induced subgraph on four vertices is an independent pair of edges. The numberv of vertices in such a graph does not exceed 5r/2; this proves a conjecture of Bermond. More generally, it is conjectured that ifv>2r, then the ratiov/r must be a rational number of the form 2+1/(2k). This is proved forv/r≥21/10. The extremal graphs and many other classes of these graphs are described and characterized. Research supported in part by the National Science Foundation under ISP 80110451. Research supported in part by the National Science Foundation under DMS-8401281. Research supported in part by the National Science Foundation under DMS-8504322, and by the Office of Naval Research under N00014-85K0570.     

On the independence number of random cubic graphs

We show that as n→∞, the independence number α(G), for almost all 3-regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ?)n, for any constant ?>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.     

1-factor covers of regular graphs

We consider minimal 1-factor covers of regular multigraphs, focusing on those that are 1-factorizations. In particular, we classify cubic graphs such that every minimal 1-factor cover is also a 1-factorization, and also classify simple regular bipartite graphs with this property. For r>3, we show that there are finitely many simple r-regular graphs such that every minimal 1-factor cover is also a 1-factorization.     

Vertex-magic labelings of regular graphs II

Previously the first author has shown how to construct vertex-magic total labelings (VMTLs) for large families of regular graphs. The construction proceeds by successively adding arbitrary 2-factors to a regular graph of order n which possesses a strong VMTL, to produce a regular graph of the same order but larger size. In this paper, we exploit this construction method. We are able to show that for any r≥4, every r-regular graph of odd order n≤17 has a strong VMTL. We show how to produce strong labelings for some families of 2-regular graphs since these are used as the starting points of our construction. While even-order regular graphs are much harder to deal with, we introduce ‘mirror’ labelings which provide a suitable starting point from which the construction can proceed. We are able to show that several large classes of r-regular graphs of even order (including some Hamiltonian graphs) have VMTLs.     

Regular subgraphs of almost regular graphs

Suppose every vertex of a graph G has degree k or k + 1 and at least one vertex has degree k + 1. It is shown that if k ≥ 2q ? 2 and q is a prime power then G contains a q-regular subgraph (and hence an r-regular subgraph for all r < q, r ≡ q (mod 2)). It is also proved that every simple graph with maximal degree Δ ≥ 2q ? 2 and average degree $\text{d > (}\text{(2q ? 2)}\text{(2q ? 1)}\text{)(Δ + 1)}$, where q is a prime power, contains a q-regular subgraph (and hence an r-regular subgraph for all r < q, r ≡ q (mod 2)). These results follow from Chevalley's and Olson's theorems on congruences.     

Graphs with homeomorphically irreducible spanning trees

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.     

Clique-inserted-graphs and spectral dynamics of clique-inserting

Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph G of degree r>0, the graph obtained by replacing every vertex of G with a complete graph of order r is called the clique-inserted-graph of G, denoted as C(G). We obtain a formula for the characteristic polynomial of C(G) in terms of the characteristic polynomial of G. Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph G. For any r-regular graph G with r>2, let S(G) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of G. We discover that the set of limit points of S(G) is a fractal with the maximum r and the minimum −2, and that the fractal is independent of the structure of the concerned regular graph G as long as the degree r of G is fixed. It follows that for any integer r>2 there exist infinitely many connected r-regular graphs (or, non-regular graphs with r as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any kth iterated clique-inserted-graph and other related results.     

Representing groups by graphs with constant link and hypergraphs

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. We prove that for any finite group Γ and any disconnected link graph L with at least three vertices there are infinitely many connected graphs G with constant link L and AutG ? Γ. We look at the analogous problem for connected link graphs, namely, link graphs that are paths or have disconnected complements. Furthermore we prove that for n, r ≥ 2, but not n = 2 = r, any finite group can be represented by infinitely many connected r-uniform, n-regular hypergraphs of arbitrarily large girth.     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

Graphs of arbitrary excessive class

We show that there exists a family of r-regular graphs of arbitrarily large excessive index for each integer r greater than 3. Furthermore, we answer a question in Bonisoli and Cariolaro (2007) [1] showing that all the positive integers can be attained as excessive classes of regular graphs.     

Extensions of some factorization results from simple graphs to multigraphs

It was shown in a recent paper that an rs-regular multigraph G with maximum multiplicity μ(G) ≤ r can be factored into r regular simple graphs if first we allow the deletion of a relatively small number of hamilton cycles from G. In this paper, we use this theorem to obtain extensions of some factorization results on simple graphs to new results on multigraphs. © 1997 John Wiley & Sons, Inc. Inc.     

A neighborhood condition which implies the existence of a class of d-chromatic subgraphs

A graph G of order n satisfies the neighborhood condition NC_k > s if any collection of k independent vertices is collectively adjacent to more than s vertices. Given a family H of graphs, the decomposition class β(H) is the family of graphs B with the property that for some H ∈ H of chromatic number d, H contains B as an induced subgraph and l?V(H) ? V(B)? is (d ? 2) colorable. Let H be a family of d-chromatic graphs, B an element of β(H) such that B contains an s-matching as an induced subgraph. Thus the cardinality of one of the partite sets of B is s + r for some integer r ≥ 0. We show that if t is a fixed positive integer, G is a graph of sufficiently large order n that satisfies the neighborhood condition then G contains B + K(d - 2; t) as a subgraph.     

On the Chromatic Number of H-Free Graphs of Large Minimum Degree

The problem of determining the chromatic number of H-free graphs has been well studied, with particular attention to K _r -free graphs with large minimum degree. Recent progress has been made for triangle-free graphs on n vertices with minimum degree larger than n/3. In this paper, we determine the family of r-colorable graphs H_r{\mathcal{H}_r}, such that if H ? H_r{H \in \mathcal{H}_r}, there exists a constant C < (r − 2)/(r − 1) such that any H-free graph G on n vertices with δ(G) > Cn has chromatic number bounded above by a function dependent only on H and C. A value of C < (r − 2)/(r − 1) is given for every H ? H_r{H \in \mathcal{H}_r}, with particular attention to the case when χ(H) = 3.     

Zero-Sum Flows in Regular Graphs

For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)²-flow. Finally, the existence of k-flows for small graphs is investigated.     

Sparse color-critical graphs and hypergraphs with no short cycles

We give constructions of color-critical graphs and hypergraphs with no short cycles and with relatively few edges. In particular, we show that, for each n ≧ 3, the smallest number of edges in a 3-critical triangle-free n-graph (hypergraph) with m vertices is m + o(m) as m → ∞. Also, for each r ≧ 4, there exists an r-critical triangle-free 2-graph (graph) with m vertices and at most (r ? (7/3))m + o(m) edges. Weaker results are obtained for the existence of r-critical graphs containing no cycle of length at most / > 3.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.