On component factors

LetK be a connected graph. A spanning subgraphF ofG is called aK-factor if every component ofF is isomorphic toK. On the existence ofK-factors we show the following theorem: LetG andK be connected graphs andp be an integer. Suppose|G| = n|K| and 1 <p < n. Also suppose every induced connected subgraph of orderp|K| has aK-factor. ThenG has aK-factor.     

Note on Perfect Forests in Digraphs

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex x in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP‐hard, for the three others this problem is polynomial‐time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.     

On even circuit decompositions of eulerian graphs

Let G be an eulerian graph without odd block. It was proved by P. D. Seymour that if G is planar, then E(G) has a circuit decomposition F such that each circuit of F is of even length. In this paper the theorem of Seymour is generalized: If G contains no subgraph contractible to K₅, then E(G) has an even circuit decomposition.     

Note on Perfect Forests

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex x in F is odd, and each tree of F is an induced subgraph of G. We provide a short linear‐algebraic proof of the following theorem of A. D. Scott (Graphs Combin 17 (2001), 539–553): A connected graph G contains a perfect forest if and only if G has an even number of vertices.     

Graphs whose powers are chordal and graphs whose powers are interval graphs

The main theorem of this paper gives a forbidden induced subgraph condition on G that is sufficient for chordality of G^m. This theorem is a generalization of a theorem of Balakrishnan and Paulraja who had provided this only for m = 2. We also give a forbidden subgraph condition on G that is sufficient for chordality of G^2m. Similar conditions on G that are sufficient for G^m being an interval graph are also obtained. In addition it is easy to see, that no family of forbidden (induced) subgraphs of G is necessary for G^m being chordal or interval graph. © 1997 John Wiley & Sons, Inc.     

An algorithmic proof of Tutte's f-factor theorem

Let G be a multigraph on n vertices, possibly with loops. An f-factor is a subgraph of G with degree f_i at the ith vertex for i = 1, 2,…, n. Tutte's f-factor theorem is proved by providing an algorithm that either finds an f-factor or shows that it does not exist and does this in O(n³) operations. Note that the complexity bound is independent of the number of edges of G and the degrees f_i. The algorithm is easily altered to handle the problem of looking for a symmetric integral matrix with given row and column sums by assigning loops degree one. A (g,f)-factor is a subgraph of G with degree d_i at the ith vertex, where g_i ? d_i ? f_i, for i = 1,2,…, n. Lovasz's (g,f)-factor theorem is proved by providing an O(n³) algorithm to either find a (g,f)-factor or show one does not exist.     

The Ramsey property for graphs with forbidden complete subgraphs

The following theorem is proved: Let G be a finite graph with cl(G) = m, where cl(G) is the maximum size of a clique in G. Then for any integer r ≥ 1, there is a finite graph H, also with cl(H) = m, such that if the edges of H are r-colored in any way, then H contains an induced subgraph G′ isomorphic to G with all its edges the same color.     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

Some results on odd factors of graphs

A {1, 3, …,2n ? 1}-factor of a graph G is defined to be a spanning subgraph of G, each degree of whose vertices is one of {1, 3, …, 2n ? 1}, where n is a positive integer. In this paper, we give a sufficient condition for a graph to have a {1, 3, …, 2n ? 1}-factor.     

Nowhere-Zero 5-Flows and Even (1,2)-Factors

A graph G = (V, E) admits a nowhere-zero k-flow if there exists an orientation H = (V, A) of G and an integer flow ${\varphi:A \to \mathbb{Z}}$ such that for all ${a \in A, 0 < |\varphi(a)| < k}$ . Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set ${F \subseteq E}$ such that the degree of any vertex v in the subgraph induced by F is 1 or 2. Let us call an edge of G, F-balanced if either it belongs to F or both its ends have the same degree in F. Call a cycle of G F-even if it has an even number of F-balanced edges. A (1,2)-factor F of G is even if each cycle of G is F-even. The main result of the paper is that a cubic graph G admits a nowhere-zero 5-flow if and only if G has an even (1,2)-factor.     

A property of trees in terms of unique connected subgraphs

The following theorem is proved: Let G be a graph with p ≥ 3 points such that for some n, 3 ≤ n ≤ p, any n points lie on a unique smallest connected subgraph. Then G = C_n+1 or G is a tree, and conversely.     

On factors with all degrees odd

A {1,3,...,2n−1}-factor of a graphG is defined to be a spanning subgraph ofG each degree of whose vertices is one of {1,3,...,2n−1}, wheren is a positive integer. In this paper, we give criterions for the existence of a {1,3,...,2n−1}-factor in a tree and in a graph.     

Well-covered graphs and factors

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perfect [1,2]-factor F_G, i.e. a spanning subgraph such that each component is 1-regular or 2-regular. Here, we characterize all well-covered graphs G satisfying α(G)=α(F_G) for some perfect [1,2]-factor F_G. This class contains all well-covered graphs G without isolated vertices of order n with α?(n-1)/2, and in particular all very well-covered graphs.     

An upper bound for the Folkman number F(3, 3; 5)

Let F(p, q; r) denote the minimum number of vertices in a graph G that has the properties (1) G contains no complete subgraph on r vertices, and (2) any green-red coloring of the edges of G yields a green complete subgraph on p vertices or a red complete subgraph on q vertices. Folkman proved the existence of F(p, q; r) whenever r > max {p, q}. We show F(3, 3; 5) ≤ 17, improving a bound due to Irving and an earlier bound due to Graham and Spencer. © 1993 John Wiley & Sons, Inc.     

Induced Decompositions of Graphs

We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.     

Calculus of Functorial Morphisms

We prove that, if F, G: 𝒞 → 𝒟 are two right exact functors between two Grothendieck categories such that they commute with coproducts and U is a generator of 𝒞, then there is a bijection between Nat(F, G) and the centralizer of Hom_𝒟(F(U), G(U)) considered as an Hom_𝒞(U, U)-Hom_𝒞(U, U)-bimodule. We also prove a dual of this result and give applications to Frobenius functors between Grothendieck categories.     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

On the threshold for k-regular subgraphs of random graphs

The k-core of a graph is the largest subgraph of minimum degree at least k. We show that for k sufficiently large, the threshold for the appearance of a k-regular subgraph in the Erdős-Rényi random graph model G(n,p) is at most the threshold for the appearance of a nonempty (k+2)-core. In particular, this pins down the point of appearance of a k-regular subgraph to a window for p of width roughly 2/n for large n and moderately large k. The result is proved by using Tutte’s necessary and sufficient condition for a graph to have a k-factor.     

A linear programming formulation for the maximum complete multipartite subgraph problem

Let G be a simple undirected graph with node set V(G) and edge set E(G). We call a subset independent if F is contained in the edge set of a complete multipartite (not necessarily induced) subgraph of G, F is dependent otherwise. In this paper we characterize the independents and the minimal dependents of G. We note that every minimal dependent of G has size two if and only if G is fan and prism-free. We give a 0-1 linear programming formulation of the following problem: find the maximum weight of a complete multipartite subgraph of G, where G has nonnegative edge weights. This formulation may have an exponential number of constraints with respect to |V(G)| but we show that the continuous relaxation of this 0-1 program can be solved in polynomial time.     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.