Bilal A.Chatand S.Pirzada

1Department of Mathematical Sciences,Islamic University of Science and Technology Awantipora,Pulwama-India

2Department of Mathematics,University of Kashmir-India

Abstract.A loopless graph on n vertices in which vertices are connected at least by a and at most by b edges is called a(a,b,n)-graph.A(b,b,n)-graph is called(b,n)-graph and is denoted by (it is a complete graph),its complement byA non increasing sequence π =(d1,···,dn)of nonnegative integers is said to be(a,b,n)graphic if it is realizable by an(a,b,n)-graph.We say a simple graphic sequence π =(d1,···,dn)is potentially K4?K2∪K2-graphic if it has a a realization containing an K4?K2∪K2as a subgraph where K4is a complete graph on four vertices and K2∪K2is a set of independent edges.In this paper,we find the smallest degree sum such that every n-term graphical sequence contains K4?K2∪K2as subgraph.

Key Words:Graph,(a,b,n)-graph,potentially graphical sequences.

1 Introduction

Let G(V,E)be a simple graph(a graph without multiple edges and loops)with n vertices and m edges having vertex set V(G)={v1,v2,···,vn}.The set of all non-increasing nonnegative integer sequences π =(d1,d2,···,dn)is denoted by NSn.A sequence π ∈ NSnis said to be graphic if it is the degree sequence of a simple graph G on n vertices,and such a graph G is called a realization of π.The set of all graphic sequences in NSnis denoted by GSn.There are several famous results,Havel and Hakimi[7,8]and Erd?s and Gallai[2]which give necessary and sufficient conditions for a sequence π =(d1,d2,···,dn)to be the degree sequence of a simple graph G.Another characterization of graphical sequences can be seen in Pirzada and Yin Jian Hu[15].A graphical sequence π is potentially H-graphical if there is a realization of π containing H as a subgraph,while π is forcibly H graphical if every realization of π contains H as a subgraph.A sequence π=(d1,d2,···,dn)is said to be potentially Kr+1-graphic if there is a realization G of π containing Kr+1as a subgraph.It is shown in[4]that if π is a graphic sequence with a realization G containing H as a subgraph,then there is a realization G of π containing H with the vertices of H having|V(H)|largest degree of π.If π has a realization in which the r+1 vertices of largest degree induce a clique,then π is said to be potentially Ar+1-graphic.We know that a graphic sequence π is potentially Kk+1-graphic if and only if π is potentially Ak+1-graphic[17].The disjoint union of the graphs G1and G2is defined by G1SG2.Let Kkand Ckrespectively denote a complete graph on k vertices and a cycle on k vertices.

In order to prove our main results,the following notations,definitions and results are needed.Let G=(V(G),E(G))be a simple graph with vertex set V(G)={v1,v2,···,vn}.Thedegreeof viisdenotedby difor1≤i≤n.Then π=(d1,d2,···,dn)isthedegreesequence of G,where d1,d2,···,dnmay ben otinin creasingorder.In ordertoprove ourmainresults,we also need the following notations and results.Let π =(d1,d2,···,dn)∈ NSn,1≤k≤n.Let

Definition 1.1.A wheel graph Wnis a graph with n vertices(n≥4)formed by connecting a single vertex to all vertices of an(n?1)cycle.A wheel graph on 4 and 5 vertices are shown in Fig.1 below.

In 1960 Erd?os and Gallai gave the following necessary and sufficient condition.

Theorem 1.1(see Erd?os,Gallai[2]).Let n≥1.An even sequence π=(d1,···,dn)is graphical if and only if

is satisfied for each integer k,1≤k≤n.

Figure 1:

Theorem 1.2(see[4]).If π =(d1,d2,···,dn)is the graphic sequence with a realization G containing H as a subgraph,then there exists a realization G0of π containing H as a subgraph so that the vertices of H have the largest degrees of π.

2 (a,b,n)-graphic sequences

In this section a,b,n,m,n and l denote non-negative integers with b≥a.An(a,b,n)-graph denoted by G?is a loopless graph in which different vertices are connected at least by a and at most by b edges[9,10].A(b,b,m)-graph on m vertices denoted byand is called shortly b-graph.Clearly,=Km,where Kmis the complete graph on m vertices.A nonincreasing sequence π =(d1,···,dn)of nonnegative integers is said to be b-graphic if it is the degree sequence of an b-graph G?on n vertices and such a graph G?is referred to as a realization of π.

The fo llowing threeresults due to Chungphaisan[1]are generalizationsfrom1-graphs to b-graphs of three well-known results,one by Erd?s and Gallai[2],one by Kleitman and Wang[11],one by Fulkerson,Hoffman and McAndrew[5].

Theorem 2.1(see[1]).Let π=(d1,···,dn)be a nonincreasing sequence of non-negative integers,where the sum of the elements of π is even.Then π is b-graphic if and only if for each positive integer t≤n,

Let π =(d1,···,dn)be a nonincreasing sequence of nonnegative integers withto be the nonincreasing rearrangement of the sequence obtained from(d1,···,dk?1,dk+1,···,dn)reducing by 1 the remaining largest term that has not already been reduced b times,and repeating the procedure dktimes.π0kis called the residual sequence obtained from π by laying off dk.

Theorem 2.2(see[11]). π is b-graphic if and only ifis b-graphic.

Theorem 2.3(see[1]).Let π be an b-graphic sequence,and let G and G0be realizations of π.Then there is a sequence of r-exchanges,E1,···,Eksuch that the application of these b-exchanges to G in order will result in G0.

An extremal problem for 1-graphic sequences to be potentially-graphic was considered by Erd?os,Jacobson and Lehel[3],and solved by Gould et al.[6]and Li et al.[13,14].Recently,Yin[18]generalized this extremal problem and the Erd?os-Jacobson-Lehel conjecture from 1-graphs to b-graphs.

An(a,b,n)-graphic sequence π is said to be potentially-graphic if there exists a realization G of π containingas a subgraph.If there exists a realization G of π containingon the m vertices of highest degree in G,then π is said to be potentially-graphic.As a special case of Lemma 2.1 in[18],Yin showed that a b-graphic sequence is potentially-graphic if and only if it is potentially-graphic.If π =(d1,···,dn)has a realization G containingon those vertices having degree d1,···,dl+msuch that the vertices ofhave degree d1,···,dland the vertices ofhave degree dl+1,···,dl+m,then π is potentially-graphic.

Theorem 2.4(see Yin[19]).Let n ≥ r+s and let π =(d1,···,dn)be a nonincreasing graphic sequence.If dr+s≥r+s?2,then π is potentially Ar,s-graphic.

In the same paper Yin published a Havel-Hakimi type algorithm constructing the corresponding Sr,s-graph.

In 2014 Pirzada and Chat proved the following assertion:

Theorem 2.5(Pirzada,Chat[16]).If G1is a realization of π1=(,···,),containing Kpas a subgraph and G2is a realization of π2=(,···,)containing Kqas a subgraph,then the degree sequence π =(d1,···,dm+n)of the join of G1and G2is Kp+q-graphic.

Problem 2.1.Let H be the graph and n be the positive integer.Determine the smallest even integer σ(H,n)such that every n-term graphic sequence contains H as a subgraph.

The purpose of this paper is to solve problem 6 by taking H=W4?(K2∪K2)and we also obtain the graphic sequence of the graph when only edge size of the graph and degree of first vertex of the non-increasing sequence of integers is given.Next we find the Necessary and sufficient condition for a b-graphic sequence to be b-star graphic.

Remark 2.1.Let cl2mbe the circular ladder graph with 2m vertices,m≥3 formed by taking two copies of the cycle Cmwith corresponding vertices from each copy of Cmbeing adjacent.Let(K2m?cl2m)be the graph obtained from K2mby removing the edges of cl2m.For m≥3,it can easily be seen that(K2m?cl2m)is a 2m?4 regular graph on 2m vertices and the number of edges in this graph be 2m(m?2).Fig.2 below is an example of ladder graph on 8 vertices.

Figure 2:

3 Main results

We start with the following main results.In the following result,we obtain the graphic sequence and the degree sum of the graph when edge size and degree of first vertex is given.

Theorem 3.1.If π1=(d1,···,dn)be a graphic sequence satisfying d1=2(n?2)and|E|2=,n≥3,then,π=(2(n?2))2n,σ(π)=4n(n?2)and π realizes K2n?cl2n.

Proof.Suppose π =(d1,d2,···,dn)be a graphic sequence with d1=2(n?2),then there exists a graph G which realizes π.Now we have

From this equation we see that every term of L.H.S is positive for every i,j and R.H.S is equal to zero.Therefore above equation is possible when di=djfor every i,j=1,2,···,2n.Since d1=2(n?2),therefore d2=d1=2(n?2)and hence dk=2(n?2)for all k=1,2,···,2n.Thus π=(2(n?2))2n.Further σ(π)=2n×2(n?2)=4n(n?2).

Figure 3:

Now from Remark 2.1,we see that π is the graphic sequence of the graph K2n?cl2n.Therefore π realizes K2n?cl2n.

In the following result,we find the smallest graphic sum such that every n-term graphic sequence contains W4?(K2∪K2)as a subgraph.

Theorem 3.2.If π be the graphic sequence with σ(π)≥3n?1 if n is odd and σ(π)≥3n?2 if n is even,then π is potentially W4?(K2∪K2)-graphic.

Proof.Let π be the graphic sequence.then there exists a graph G which realizes π.We have to show that if σ(π)≥3n?1 and σ(π)≥3n?2,then every n-term graphic sequence contains W4?(K2∪K2)as a subgraph,where K2∪K2is the matching in G.To prove the result we use induction on n and we start induction for n≥4.For n=4,then by the assumption we have|E|≥ 5,therefore in this case the realization G of π contains W4?(K2∪K2)as a subgraph as illustrated in Fig.3.

Clearly from Fig.3,there are exactly two graphs with|G|=4 and|E|≥5 and both these graphs contains W4?(K2∪K2)as a subgraph.Thus π is potentially W4?(K2∪K2)-graphic.Now for n=5,therefore from give assumption we have|E|≥7,then there are exactly four graphic sequences(4,32,22),(4,33,1),(34,2)and(42,23)with σ(π)=14 and each of these graphic sequences have a realization G containing W4?(K2∪K2)as a subgraph as illustrated in Fig.4.

All these graphs contains W4?(K2∪K2)and the result is true in this case also.Now assume that the result is true for all graphic sequences of n-terms and we now consider the graphic sequences of n+1 terms.Now if the graphic sequence π contains a vertex of degree equal to 1,then remove it and adjust the new sequence π0.By induction realization G of π0must contain a W4?(K2∪K2).We know that for n≥6 smallest degree sum such that every n-term graphic sequence contains a clique on three vertices is 2n.Since σ(π)=16 for n=6 which is greater than the smallest degree sum such that every 6-term graphic sequence contains a clique on 3 vertices which can be obtained in a realization using the two vertices of highest degree.Let this complete graph graph on three vertices has vertices y1,y2and y3and assume that these two vertices of highest degree in the graph are y1and y2.Thus y1and y2have at least one more adjacency in the graph say y1is adjacent to x and y2is adjacent to y as shown in Fig.5.

Now we consider the following cases:

Figure 4:

Figure 5:

Case I.If x=y,then G contains the subgraph W4?(K2∪K2),therefore the result is true in this case.

Subcase 1.Suppose x and y have common vertex w such that xw and yw∈E(G).Then we see that wy1and xy3are not in realization G of π,since otherwise we get a realization G containing W4?(K2∪K2).Then by EDT by removing the independent edges K2∪K2(xw and y1y3)and inserts the independent edges K2∪K2(wy1and xy3)produces a realization G0of π containing a W4?(K2∪K2)on the vertex set S={y1,y2,w,y}.

Subcase 2.Suppose that x and y have no common adjacency of a clique on three vertices.Suppose x is adjacent to x0and y is adjacent to y0such that x06y0.Now suppose that x0y0

Figure 7:

E(G),then by EDT that removes the independent edges K2∪K2(xx0and yy0)and inserts theindependentedges x0y0and xy producesarealization G of π containingW4?(K2∪K2).These two subcases are illustrated in Figs.6 and 7 below.

Subcase 3.Now if x0y0∈E(G),then again it is easy to see that the independent edges x1y1and xy3E(G),since otherwise W4?(K2∪K2)would exist.Therefore again by EDT that removes the independent edges y1y3and xx0and inserts the independent edges y1x0and xy2producesarealization G of π containingW4?(K2∪K2).ThusinallcasesW4?(K2∪K2)was prod ucedins omerealizationof π andther ef oretheg raphicsequence π ispotentially W4?(K2∪K2)and hence the result is proved.

Example 3.1.Let π1=(4,33,1)be the non-negative sequence.Then clearly it is graphic with σ(π)=14.Therefore by above theorem realization of π contains H=W4?(K2∪K2)as a subgraph.Thus π1is potentially H-graphic.

Example 3.2.Let π2=(32,23)be the non-negative sequence.Then clearly it is graphic with σ(π)=12.Therefore by above theorem every 5-term graphic sequence of π does not contains H=W4?(K2∪K2)as a subgraph.Thus every 5-term graphic sequence of π2does not contain H as a subgraph.

Next we obtain the following results on(a,b,n)-graphic sequences.

Lemma 3.1.An(a,b,n)-graph G?is r-regular if and only if

Proof.Suppose(a,b,n)-graph G?is r-regular,then 2|E|=nr and di=r for all i=1,2,···,n.Therefore,we have

Theorem 3.3.Let G?be(a,b,n)-graph with n≥2,then G?is a b-complete graphiff

Proof.Suppose that G?is b-complete on n vertices with n≥2.Then by Remark 2.2,|E|=(n?1).Therefore

Conversely suppose that the graph G(a,b,n)holds

Therefore by Lemma 3.1,we have

Therefore,by Remark 2.2 G?is b-complete graph

Theorem 3.4.If a multigraph G?is b-complete bipartite graphthen G?is a b-star graphif

Proof.Suppose that the multigraph G?=where s is greater than 1.Since there are rverticese ach of whose degreeis b×s riceseachofwhosedegreeis b×r.Therefore we haveNow,from the above it follows that n=r+s and|E|=brs.Therefore,we have

Now suppose that

Thus we have proved that a multigraph G?is a b star graph if

So,we complete the proof.

Corollary 3.1.Let G?be complete multibibartite graph,if G?is Kb1,n?1,then

Proof.Suppose that a complete multi-bipartite graph is.Then we have

Thus,we complete the proof.

Acknowledgements

The authors would like to thank the reviewer for his valuable comments and suggestions,which led to a great improvement of the original manuscript.