{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.     

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 sequence and supereulerian graphs

A sequence d=(d₁,d₂,…,d_n) is graphic if there is a simple graph G with degree sequence d, and such a graph G is called a realization of d. A graphic sequence d is line-hamiltonian if d has a realization G such that L(G) is hamiltonian, and is supereulerian if d has a realization G with a spanning eulerian subgraph. In this paper, it is proved that a nonincreasing graphic sequence d=(d₁,d₂,…,d_n) has a supereulerian realization if and only if d_n≥2 and that d is line-hamiltonian if and only if either d₁=n−1, or ∑_di=1d_i≤∑_dj≥2(d_j−2).     

Connected even factors in claw-free graphs

A connected even [2,2s]-factor of a graph G is a connected factor with all vertices of degree i (i=2,4,…,2s), where s?1 is an integer. In this paper, we show that every supereulerian K_1,s-free graph (s?2) contains a connected even [2,2s-2]-factor, hereby generalizing the result that every 4-connected claw-free graph has a connected [2,4]-factor by Broersma, Kriesell and Ryjacek.     

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d₁≤d₂≤?≤d_n satisfies: for k<n/2, d_k≤min{k+ηn,n/2} implies d_n−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G).     

Bounds for the error of linear systems of equations using the theory of moments

Consider the system, of linear equations Ax = b where A is an n × n real symmetric, positive definite matrix and b is a known vector. Suppose we are given an approximation to x, ξ, and we wish to determine upper and lower bounds for ∥ x − ξ ∥ where ∥ ··· ∥ indicates the euclidean norm. Given the sequence of vectors {r_i}_{i^k = 0}, where r_i = Ar_{i − 1} and r₀ = b − Aξ, it is shown how to construct a sequence of upper and lower bounds for ∥ x − ξ ∥ using the theory of moments.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

Rose window graphs underlying rotary maps

Given natural numbers n≥3 and 1≤a,r≤n−1, the rose window graph R_n(a,r) is a quartic graph with vertex set {x_i∣i∈Z_n}∪{y_i∣i∈Z_n} and edge set {{x_i,x_i+1}∣i∈Z_n}∪{{y_i,y_i+r}∣i∈Z_n}∪{{x_i,y_i}∣i∈Z_n}∪{{x_i+a,y_i}∣i∈Z_n}. In this paper rotary maps on rose window graphs are considered. In particular, we answer the question posed in [S. Wilson, Rose window graphs, Ars Math. Contemp. 1 (2008), 7-19. http://amc.imfm.si/index.php/amc/issue/view/5] concerning which of these graphs underlie a rotary map.     

Non-separating 2-factors of an even-regular graph

For a 2-factor F of a connected graph G, we consider G−F, which is the graph obtained from G by removing all the edges of F. If G−F is connected, F is said to be a non-separating 2-factor. In this paper we study a sufficient condition for a 2r-regular connected graph G to have such a 2-factor. As a result, we show that a 2r-regular connected graph G has a non-separating 2-factor whenever the number of vertices of G does not exceed 2r²+r.     

A preferential attachment model with random initial degrees

In this paper, a random graph process {G(t)} _t≥1 is studied and its degree sequence is analyzed. Let {W _t } _t≥1 be an i.i.d. sequence. The graph process is defined so that, at each integer time t, a new vertex with W _t edges attached to it, is added to the graph. The new edges added at time t are then preferentially connected to older vertices, i.e., conditionally on G(t-1), the probability that a given edge of vertex t is connected to vertex i is proportional to d _i (t-1)+δ, where d _i (t-1) is the degree of vertex i at time t-1, independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent τ=min{τ_W,τ_P}, where τ_W is the power-law exponent of the initial degrees {W _t } _t≥1 and τ_P the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze.     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

A remark on degree sequences of multigraphs

A sequence {d ₁, d ₂, . . . , d _n } of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v ₁, v ₂, . . . , v _n such that the degree d(v _i ) of the vertex v _i equals d _i for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow.     

The k-factor conjecture is true

A sequence 〈d_i〉, 1≤i≤n, is called graphical if there exists a graph whose i^th vertex has degree d_i for all i. It is shown that the sequences 〈d_i〉 and 〈d_i-k〉 are graphical only if there exists a graph G whose degree sequence is 〈d_i〉 and which has a regular subgraph with k lines at each vertex. Similar theorems have been obtained for digraphs. These theorems resolve comjectures given by A.R. Rao and S.B. Rao, and by B. Grünbaum.     

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.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

The {k}-domatic number of a graph

For a positive integer k, a {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0, 1, 2, . . . , k} such that for any vertex ${v\in V(G)}$ , the condition ${\sum_{u\in N[v]}f(u)\ge k}$ is fulfilled, where N[v] is the closed neighborhood of v. A {1}-dominating function is the same as ordinary domination. A set {f ₁, f ₂, . . . , f _d } of {k}-dominating functions on G with the property that ${\sum_{i=1}^df_i(v)\le k}$ for each ${v\in V(G)}$ , is called a {k}-dominating family (of functions) on G. The maximum number of functions in a {k}-dominating family on G is the {k}-domatic number of G, denoted by d _{k}(G). Note that d _{1}(G) is the classical domatic number d(G). In this paper we initiate the study of the {k}-domatic number in graphs and we present some bounds for d _{k}(G). Many of the known bounds of d(G) are immediate consequences of our results.     

Distributing vertices along a Hamiltonian cycle in Dirac graphs

A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are ω,n₀>0 such that if G is a Dirac graph on n≥n₀ vertices, d is an arbitrary integer with 3≤d≤ωn/2 and S is an arbitrary subset of the vertices of G with 2≤|S|=k≤ωn/d, then for every sequence d_i of integers with 3≤d_i≤d,1≤i≤k−1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a₁,a₂,…,a_k, such that the vertices of S are visited in this order on C and we have

     

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 connectivity and superconnected graphs with small diameter

In this paper, first we prove that any graph G is 2-connected if diam(G)≤g−1 for even girth g, and for odd girth g and maximum degree Δ≤2δ−1 where δ is the minimum degree. Moreover, we prove that any graph G of diameter diam(G)≤g−2 satisfies that (i) G is 5-connected for even girth g and Δ≤2δ−5, and (ii) G is super-κ for odd girth g and Δ≤3δ/2−1.