Search

The Turán number of a graph H , denoted by ex (n , H) , is the maximum number of edges of an n -vertex simple graph having no H as a subgraph. Let k K p + 1 denote the disjoint union of k copies of graph K p + 1. There are very few cases when the Turán number ex (n , k K p + 1) is known exactly for n ≥ k p + k. Erdős and Gallai determined ex (n , k K 2) for n ≥ 2 k. Chen, Lu and Yuan determined ex (n , 2 K p + 1) for n ≥ 2 p + 2. In this paper, we further determine ex (n , 3 K p + 1) for n ≥ 3 p + 3. [ABSTRACT FROM AUTHOR]

Given a distribution of pebbles on the vertices of a connected graph G , a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number π ( G ) is the smallest positive integer such that for every distribution of π ( G ) pebbles and every vertex v , a pebble can be moved to v . Graham conjectured that π ( G □ H ) ≤ π ( G ) π ( H ) for any connected graphs G and H , where G □ H denotes the Cartesian product of G and H . A graph G has the 2-pebbling property (respectively, the odd-2-pebbling property ) if for any distribution with more than 2 π ( G ) − q (respectively, 2 π ( G ) − r ) pebbles, where q is the number of vertices with at least one pebble (respectively, r is the number of vertices with an odd number of pebbles), it is possible, using pebbling moves, to get two pebbles to any vertex. Obviously, graphs which have the 2-pebbling property also have the odd-2-pebbling property. A graph G without the 2-pebbling property is called a Lemke graph . In this paper, we further extend the concept of the odd-2-pebbling property to the weak odd-2-pebbling property and show that all Lemke graphs found to date have the weak odd- 2 -pebbling property, but not the odd- 2 -pebbling property. Moreover, we also prove that π ( L □ T ) ≤ π ( L ) π ( T ) and π ( L □ K n ) ≤ π ( L ) π ( K n ) , where T is a tree, K n is the complete graph on n vertices and L is a known Lemke graph. The two evidences supporting Graham’s conjecture differ from the previous evidences requiring that G and H have the 2-pebbling property. [ABSTRACT FROM AUTHOR]

Let S = ( a 1 , … , a m ; b 1 , … , b n ) be a pair of two nonincreasing sequences of positive integers, that is, a 1 , … , a m and b 1 , … , b n are two nonincreasing sequences of positive integers. The pair S = ( a 1 , … , a m ; b 1 , … , b n ) is said to be a bigraphic pair if there is a simple bipartite graph G = ( X ∪ Y , E ) such that a 1 , … , a m and b 1 , … , b n are the degrees of the vertices in X and Y , respectively. In this paper, we give a simple sufficient condition for a pair S = ( a 1 , … , a m ; b 1 , … , b n ) to be a bigraphic pair. The condition depends only on the lengths of two sequences of the pair and their largest and smallest elements. This result extends a result due to Alon et al. (2010). [ABSTRACT FROM AUTHOR]

Let S = ( a 1 , … , a m ; b 1 , … , b n ) , where a 1 , … , a m and b 1 , … , b n are two nonincreasing sequences of nonnegative integers. The pair S = ( a 1 , … , a m ; b 1 , … , b n ) is said to be a bigraphic pair if there is a simple bipartite graph G = ( X ∪ Y , E ) such that a 1 , … , a m and b 1 , … , b n are the degrees of the vertices in X and Y , respectively. Let A be an (additive) Abelian group. We define σ ( A , m , n ) to be the minimum integer k such that every bigraphic pair S = ( a 1 , … , a m ; b 1 , … , b n ) with a m , b n ≥ 2 and σ ( S ) = a 1 + ⋯ + a m ≥ k has an A -connected realization. In this paper, we determine the values of σ ( Z 3 , m , m ) for m ≥ 4 . [ABSTRACT FROM AUTHOR]

A nonnegative integer n -tuple ( d 1 , … , d n ) (not necessarily monotone) is graphic if there is a simple graph G with the vertex set { v 1 , … , v n } in which the degree of v i is d i . Graphic n -tuples ( d 1 ( 1 ) , … , d n ( 1 ) ) and ( d 1 ( 2 ) , … , d n ( 2 ) ) pack if there are edge-disjoint n -vertex graphs G 1 and G 2 with the same vertex set { v 1 , … , v n } such that d G 1 ( v i ) = d i ( 1 ) and d G 2 ( v i ) = d i ( 2 ) for all i . Let Δ ( π ) and δ ( π ) denote the largest and smallest entries in n -tuple π respectively. For graphic n -tuples π 1 and π 2 , Busch et al. (2012) proved that if Δ ( π 1 + π 2 ) ≤ 2 δ ( π 1 + π 2 ) n − ( δ ( π 1 + π 2 ) − 1 ) (strict inequality when δ ( π 1 + π 2 ) = 1 ), then π 1 and π 2 pack. As a more direct analogue to the Sauer–Spencer Theorem, Busch et al. conjectured that if δ ( π 1 + π 2 ) ≥ 1 and the product of corresponding entries in π 1 and π 2 is always less than n 2 , then π 1 and π 2 pack. In this paper, we prove that if δ ( π 1 ) ≥ 1 , π 2 is an almost k -regular graphic n -tuple with k ≥ 1 , and the product of corresponding entries in π 1 and π 2 is always less than n 2 , then π 1 and π 2 pack. This is an interesting variation of Kundu’s Theorem. Combining this result with a counterexample to the above conjecture of Busch et al., we present a slight modification of this conjecture as follows: if δ ( π 1 ) ≥ 1 , δ ( π 2 ) ≥ 1 and the product of corresponding entries in π 1 and π 2 is always less than n 2 , then π 1 and π 2 pack. [ABSTRACT FROM AUTHOR]

The Turán number of a graph H , denoted by e x (n , H) , is the maximum number of edges of an n -vertex simple graph having no H as a subgraph. Let S ℓ denote the star on ℓ + 1 vertices, and let k ⋅ S ℓ denote the disjoint union of k copies of S ℓ. Erdős and Gallai determined e x (n , k ⋅ S 1) for all positive integers k and n. Yuan and Zhang determined e x (n , k ⋅ S 2) and characterized all extremal graphs for all positive integers k and n. Lidický et al. determined e x (n , k ⋅ S ℓ) for k , ℓ ≥ 1 and n sufficiently large. Lan et al. determined e x (n , k ⋅ S ℓ) for k ≥ 2 , ℓ ≥ 3 and n ≥ k (ℓ 2 + ℓ + 1) − ℓ 2 (ℓ − 3). In this paper, we completely determine e x (n , k ⋅ S ℓ) for all positive integers k , ℓ and n. [ABSTRACT FROM AUTHOR]

Abstract: Given a distribution of pebbles on the vertices of a connected graph , a pebbling move on consists of taking two pebbles off one vertex, throwing one away, and putting the other pebble on an adjacent vertex. The t-pebbling number of a connected graph is the smallest positive integer such that from every distribution of pebbles on , pebbles can be moved to any specified target vertex of . For , Graham conjectured that for any connected graphs and , where denotes the Cartesian product of and . Herscovici and Higgins [D.S. Herscovici, A.W. Higgins, The pebbling number of , Discrete Math. 187 (1998) 123–135] proved that . Herscovici [D.S. Herscovici, Graham’s pebbling conjecture on products of many cycles, Discrete Math. 308 (2008) 6501–6512] conjectured that if , then . In this paper, we confirm this conjecture. [Copyright &y& Elsevier]

Abstract: Let be a graphic list , where and . If each realization of is -connected, then is said to be forcibly -connected. If for and for , then is said to satisfy the Pósa Condition. In this paper, we prove that if satisfies the Pósa Condition with and , then is forcibly -connected. This answers a question posed by Yin and Zhang [J.H. Yin, Y. Zhang, Pósa-condition and nowhere-zero 3-flows, Discrete Math. 311 (2011) 897–907]. [Copyright &y& Elsevier]

Abstract: For a given graph , a non-increasing sequence of nonnegative integers is said to be potentially -graphic if there exists a realization of containing as a subgraph. The split graph on vertices is denoted by . In this paper, we give a Rao-type characterization for to be potentially -graphic. A simplification of this characterization is also presented. [Copyright &y& Elsevier]

Abstract: Let be a simple graph on vertices and be the degree sequence of , where and . The classical Pósa’s theorem states that if for and for being odd and , then is Hamiltonian, which implies that admits a nowhere-zero 4-flow. In this paper, we further show that if satisfies the Pósa-condition that for and for being odd and , then has no nowhere-zero 3-flow if and only if is one of seven completely described graphs. [Copyright &y& Elsevier]

Abstract: Given a distribution of pebbles on the vertices of a connected graph , a pebbling move on consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number is the smallest number such that, for every distribution of pebbles and every vertex , a pebble can be moved to . A graph is said to have the2-pebbling property if, for any distribution with more than pebbles, where is the number of vertices with at least one pebble, it is possible, using pebbling moves, to get two pebbles to any vertex. A graph without the 2-pebbling property is called a Lemke graph. Snevily and Foster [H.S. Snevily, J.A. Foster, The 2-pebbling property and a conjecture of Graham’s, Graphs and Combin. 16 (2000), 231–244] defined an infinite family of possible Lemke graphs, and conjectured that is a Lemke graph for each . In this paper, we prove this conjecture. [Copyright &y& Elsevier]

Abstract: An -graph is a loopless undirected graph in which no two vertices are joined by more than edges. An -complete graph on vertices, denoted by , is an -graph on vertices in which each pair of vertices is joined by exactly edges. A non-increasing sequence of nonnegative integers is said to be -graphic if it is realizable by an -graph on vertices. An -graphic sequence is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for -graphic sequences to be potentially -graphic are given. These are generalizations from -graphs to -graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544]. [Copyright &y& Elsevier]

Abstract: An -graph is a loopless undirected graph in which no two vertices are joined by more than edges. An -complete graph on vertices, denoted by , is an -graph on vertices in which each pair of vertices is joined by exactly edges. A non-increasing sequence of nonnegative integers is -graphic if it is realizable by an -graph on vertices. Let be the smallest even integer such that each -term -graphic sequence with term sum of at least is realizable by an -graph containing as a subgraph. In this paper, we determine the value of for sufficiently large , which generalizes a conjecture due to Erdős, Jacobson and Lehel. [Copyright &y& Elsevier]

Abstract: 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 , determine the smallest even integer such that every -term graphic sequence with term sum has a realization containing as a subgraph. Let denote the generalized friendship graph on vertices, that is, the graph of copies of meeting in a common set, where is the complete graph on vertices and . In this paper, we determine for , , and sufficiently large. [Copyright &y& Elsevier]

Abstract: A variation of a classical Turán-type extremal problem is considered as follows: determine the smallest even integer such that every n-term graphic sequence with term sum has a realization G containing as a subgraph. In this paper, we determine for sufficiently large n, where and . [Copyright &y& Elsevier]

Abstract: A graphic sequence is said to be potentially -graphic, if has a realization G containing , a clique of vertices, as a subgraph. In this paper, we give two simple sufficient conditions for a graphic sequence to be potentially -graphic. We also show that the two sufficient conditions imply a theorem due to Rao [An Erdös-Gallai type result on the clique number of a realization of a degree sequence unpublished.], a theorem due to Li et al [The Erdös–Jacobson–Lehel conjecture on potentially -graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.], the Erdös–Jacobson–Lehel conjecture on which was confirmed (see [Potentially -graphical degree sequences, in: Y. Alavi et al. (Eds.), Combinatorics, Graph Theory, and Algorithms, vol. 1, New Issues Press, Kalamazoo Michigan, 1999, pp. 451–460; The smallest degree sum that yields potentially -graphic sequences, J. Graph Theory 29 (1998) 63–72; An extremal problem on the potentially -graphic sequence, Discrete Math. 212 (2000) 223–231; The Erdös–Jacobson–Lehel conjecture on potentially -graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.]) and the Yin–Li–Mao conjecture on [An extremal problem on the potentially -graphic sequences, Ars Combin. 74 (2005) 151–159.], where is a graph obtained by deleting one edge from . [Copyright &y& Elsevier]

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2+⋯+dn⩾σ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ⩾7 and 3⩽k⩽ℓ, we completely determine the smallest even integer σ(kCℓ,n) such that each n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2+⋯+dn⩾σ(kCℓ,n) has a realization G containing a cycle of length r for each r, k⩽r⩽ℓ. [Copyright &y& Elsevier]

We consider a variation of a classical Tura´n-type extremal problem (F. Chung, R. Graham, Erdo˝s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(Kr,s,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2+⋯+dn⩾σ(Kr,s,n) is potentially Kr,s-graphic, where Kr,s is a r×s complete bipartite graph, i.e., π has a realization G containing Kr,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially Kr,s-graphic, and then we determine σ(Kr,r,n) for r=3,4. [Copyright &y& Elsevier]

Abstract: Let and be nonincreasing lists of nonnegative integers, having lengths and , respectively. The pair is potentially -bigraphic if there is a simple bipartite graph containing (with vertices in the part of size and in the part of size ) such that the lists of vertex degrees in the two partite sets are and . We give a characterization of potentially -bigraphic pairs, generalizing the Gale–Ryser characterization of bigraphic pairs. [Copyright &y& Elsevier]

The Turán number of a graph H , denoted by e x (n , H) , is the maximum number of edges of an n -vertex simple graph having no H as a subgraph. Let S ℓ denote the star on ℓ + 1 vertices, and let k ⋅ S ℓ denote k disjoint copies of S ℓ. Erdős and Gallai determined the value e x (n , k ⋅ S 1) for all positive integers k and n. Yuan and Zhang determined the value e x (n , k ⋅ S 2) and characterized all extremal graphs for all positive integers k and n. Recently, Lan et al. determined the value e x (n , 2 ⋅ S 3) for all positive integers n. In this paper, we first determine the Turán number e x (n , 2 ⋅ S ℓ) for all positive integers ℓ (≥ 4) and n , and then determine the Turán number e x (n , 3 ⋅ S ℓ) for all positive integers ℓ (≥ 3) and n , improving two of the results of Lidický et al. [ABSTRACT FROM AUTHOR]