Minimal Elements in the Poset of Graphic Sequences

A nonincreasing sequence ( of n nonnegative integers is said to be graphic if it is the degree sequence of a simple graph G of order n. The set of all graphic sequences of n terms with even sum 2m and trace f is a poset G_(n,m,f) under majorization relation. The paper characterizes the minimal elements in the poset G_(n,m,f) and determines the number of minimal elements in various posets of graphic sequences.

Graphic Sequences and Split Graphs

The split graph Kr∨Ks on r＋s vertices is denoted by Sr,s A graphic sequence π = （d1, d2, …, dn） is said to be potentially Sr,s-graphic if there is a realization of π containing Sr,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially Sr,s-graphic is obtained, which extends an analogous condition for π to be potentially Kr＋1-graphic due to Yin and Li （Discrete Math. 301 （2005） 218-227）. As an application of this condition, we further determine the values of δ（Sr,s, n） for n _≥3＋ 3s - 1.

Exact Solution to an Extremal Problem on Graphic Sequences with a Realization Containing Every 2-Tree on k Vertices

A simple graph G is a 2-tree if G=K3,or G has a vertex v of degree 2,whose neighbors are adjacent,and G-v is a 2-tree.Clearly,if G is a 2-tree on n vertices,then |E(G)|=2 n-3.A non-increasing sequence π=(d1,...,dn) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.[Acta Math.Sin.Engl.Ser.,25,795-802(2009)] proved that if k≥2,n≥9/2 k^22+19/2 k and π=(d1,...,dn) is a graphic sequence with∑i=1^n di>(k-2)n,then π has a realization containing every 1-tree(the usual tree) on k vertices.Moreover,the lower bound(k-2)n is the best possible.This is a variation of a conjecture due to Erdos and Sos.In this paper,we investigate an analogue problem for 2-trees and prove that if k≥3 is an integer with k≡i(mod 3),n≥ 20[k/3] 2+31[k/3]+12 and π=(d1,...,dn) is a graphic sequence with ∑i=1^n di>max{k-1)(n-1), 2 [2 k/3] n-2 n-[2 k/3] 2+[2 k/3]+1-(-1)i}, then π has a realization containing every 2-tree on k vertices.Moreover,the lower bound max{(k-1)(n-1), 2[2 k/3]n-2 n-[2 k/3] 2+[2 k/3]+1-(-1)i}is the best possible.This result implies a conjecture due to [Discrete Math.Theor.Comput.Sci.,17(3),315-326(2016)].

A New Sufficient Degree Condition for a Graphic Sequence to Be Forcibly k-Edge-Connected

A graphic sequence π =(d1, d2,..., dn) is said to be forcibly k-edge-connected if every realization of π is k-edge-connected. In this paper, we obtain a new sufficient degree condition for π to be forcibly k-edgeconnected. We also show that this new sufficient degree condition implies a strongest monotone degree condition for π to be forcibly 2-edge-connected and a conjecture about a strongest monotone degree condition for π to be forcibly 3-edge-connected due to Bauer et al.(Networks, 54(2)(2009) 95-98), and also implies a strongest monotone degree condition for π to be forcibly 4-edge-connected.

A New Lower Bound on the Potential-Ramsey Number of Two Graphs

A nonincreasing sequenceπ=(d1,…,dn)of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.In this case,G is referred to as a realization ofπ.Given a graph H,a graphic sequenceπis potentially H-graphic ifπhas a realization containing H as a subgraph.For graphs G1 and G2,the potential-Ramsey number rpot(G1,G2)is the smallest integer k such that for every k-term graphic sequenceπ,eitherπis potentially G1-graphic or the complementary sequenceπ=(k-1-dk,…,k-1-d1)is potentially G2-graphic.For 0≤k≤[t/2],denote Kt-k to be the graph obtained from Kt by deleting k independent edges.If k=0,Busch et al.(Graphs Combin.,30(2014)847-859)present a lower bound on rpot(G,Kt)by using the 1-dependence number of G.In this paper,we utilize i-dependence number of G for i≥1 to give a new lower bound on rpot(G,Kt-k)for any k with 0≤k≤[T/2].Moreover,we also determine the exact values of rpot(Kn,Kt-k)for 1≤k≤2.