A Generalization of Orthogonal Factorizations in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated functions defined on V(G) such that g(x) ≤f(x) for all x∈V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤d _H (x) ≤f(x) for all x∈V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let = {F ₁, F ₂, ..., F _m } be a factorization of G and H be a subgraph of G with mr edges. If F _i , 1 ≤i≤m, has exactly r edges in common with H, then is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf−kr)-graph, where m, k and r are positive integers with k < m and g≥r, contains a subgraph R such that R has a (g, f)-factorization which is r-orthogonal to a given subgraph H with kr edges. This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China     

The Hamilton-Waterloo Problem with 4-Cycles and a Single Factor of n-Cycles

A 2-factor in a graph G is a 2-regular spanning subgraph of G, and a 2-factorization of G is a decomposition of all the edges of G into edge-disjoint 2-factors. A ${\{C_{m}^{r}, C_{n}^{s}\}}$ -factorization of K _υ asks for a 2-factorization of K _υ , where r of the 2-factors consists of m-cycles, and s of the 2-factors consists of n-cycles. This is a case of the Hamilton-Waterloo problem with uniform cycle sizes m and n. If υ is even, then it is a decomposition of K _υ ? F where a 1-factor F is removed from K _υ . We present necessary and sufficient conditions for the existence of a ${\{C_{4}^{r}, C_{n}^{1}\}}$ -factorization of K _υ ? F.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

The topological type of the α-sections of convex sets

An α=(α₁,…,αk)(0?αi?1) section of a family {K₁,…,Kk} of convex bodies in Rd is a transversal halfspace H⁺ for which Vold(Ki∩H⁺)=αi⋅Vold(Ki) for every 1?i?k. Our main result is that for any well-separated family of strictly convex sets, the space of α-sections is diffeomorphic to Sd−k.     

Weak cycle partition involving degree sum conditions

Let G be a graph of order n and k a positive integer. A set of subgraphs H={H₁,H₂,…,H_k} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H₁,…,H_k are vertex disjoint subgraphs of G such that and for all i, 1≤i≤k, H_i is a cycle or K₁ or K₂. If, in addition, for all i, 1≤i≤k, H_i is a cycle or K₁, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G has a k-DCP, except G≅C₅ and k=2. We prove that if G is a graph of order n≥k+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K₂∪K_n−2∪{e}, where e is an edge connecting V(K₂) and V(K_n−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

Arbitrarily vertex decomposable suns with few rays

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,…,n_k) of positive integers with n₁+?+n_k=n, there exists a partition (V₁,…,V_k) of the vertex set of G such that V_i induces a connected subgraph of order n_i, for all i=1,…,k. A sun with r rays is a unicyclic graph obtained by adding r hanging edges to r distinct vertices of a cycle. We characterize all arbitrarily vertex decomposable suns with at most three rays. We also provide a list of all on-line arbitrarily vertex decomposable suns with any number of rays.     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

More on the generalized Macaulay theorem

Let k₁ ? k₂ ? … ? k_n be given positive integers and let F denote the set of vectors (l₁, …, l_n) with integer components satisfying 0 ? l_i ? k_i, i = 1, 2, …, n. If H is a subset of F, let (l)H denote the subset of H consisting of those vectors with component sum l, and let C((l)H) denote the smallest [(l)H] elements of (l)F. The generalized Macaulay theorem due to the author and B. Lindström [3] shows that |Gamma;((C)(l)(H)|, ? |Γ(C((l)H))|, where Γ((l)H) is the setof vectors in F obtainable by subtracting l from a single component of a vector in (l)H. A method is given for computing [Γ(C((l)H)] in this paper. It is analogous to the method for computing |Γ(C(l)H))| in the k₁ = … = k_n = 1 case which has been given independently by Katona [4] and Kruskal [5].     

{k,r – k}-Factors of r-Regular Graphs

For a set \({\mathcal{S}}\) of positive integers, a spanning subgraph F of a graph G is called an \({\mathcal{S}}\) -factor of G if \({\deg_F(x) \in \mathcal{S}}\) for all vertices x of G, where deg _F (x) denotes the degree of x in F. We prove the following theorem on {a, b}-factors of regular graphs. Let r ≥ 5 be an odd integer and k be either an even integer such that 2 ≤ k < r/2 or an odd integer such that r/3 ≤ k < r/2. Then every r-regular graph G has a {k, r–k}-factor. Moreover, for every edge e of G, G has a {k, r–k}-factor containing e and another {k, r–k}-factor avoiding e.     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

A multiplicative inequality for vertex Folkman numbers

Let G be a graph and a₁,…,a_r be positive integers. The symbol G→(a₁,…,a_r) denotes that in every r-coloring of the vertex set V(G) there exists a monochromatic a_i-clique of color i for some i∈{1,…,r}. The vertex Folkman numbers F(a₁,…,a_r;q)=min{|V(G)|:G→(a₁,…,a_r) and K_q?G} are considered. Let a_i, b_i, c_i, i∈{1,…,r}, s, t be positive integers and c_i=a_ib_i, 1?a_i?s,1?b_i?t. Then we prove that

F(c₁,c₂,…,c_r;st+1)?F(a₁,a₂,…,a_r;s+1)F(b₁,b₂,…,b_r;t+1).     

Sums and k-sums in abelian groups of order k

Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence a₁,…,ar that does not have 0 as a k-sum is attained at the sequence b₁,…,br−k+1,0,…,0, where b₁,…,br−k+1 is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value k−1 times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader.     

Generalised Ramsey numbers for small graphs

The generalised Ramsey number R(G₁, G₂,..., G_k) is defined as the smallest integer n such that, if the edges of K_n, the complete graph on n vertices, are coloured using k colours C₁, C₂,..., C_k, then for some i(1≤i≤k) there is a subgraph G_i of K_n with all of its edges colour C_i. When G₁=G₂=...,G_k=G, we use the more compact notation R_k(G).The generalised Ramsey numbers R_k(G) are investigated for all graphs G having at most four vertices (and no isolates). This extends the work of Chvátal and Harary, who made this investigation in the case k=2.     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

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.     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

1-Factorizations of cartesian products of regular graphs

Let G₁, G₂…, G_n be regular graphs and H be the Cartesian product of these graphs (H = G₁ × G₂ × … × G_n). The following will be proved: If the set {G₁, G₂…, G_n} has at leat one of the following properties: (*) for at leat one i ? {1, 2,…, n}, there exists a 1-factorization of G_i or (**) there exists at least two numbers i and j such that 1 ≤ i < j ≤ n and both the Graphs G_i and G_j contain at least one 1-factor, then there exists a 1-factorization of H. Further results: Let F be a cycle of length greater than three and let G be an arbitrary cubic graph. Then there exists a 1-factorization of the 5-regular graph H = F × G. The last result shows that neither (*) nor (**) is a necessary condition for the existence of a 1-factorization of a Cartesian product of regular graphs.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.