On potentially <Emphasis Type="Italic">H</Emphasis>-graphic sequences

For given a graph H, a graphic sequence π = (d ₁, d ₂,..., d _n) is said to be potentially H-graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially (K ₅ − e)-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K ₅-graphic, where K _r is a complete graph on r vertices and K _r-e is a graph obtained from K _r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K ₆-graphic. Project supported by National Natural Science Foundation of China (No. 10401010).     

A generalization of a conjecture due to Erd?s, Jacobson and Lehel

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is r-graphic if it is realizable by an r-graph on n vertices. Let be the smallest even integer such that each n-term r-graphic sequence with term sum of at least is realizable by an r-graph containing as a subgraph. In this paper, we determine the value of for sufficiently large n, which generalizes a conjecture due to Erd?s, Jacobson and Lehel.     

A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r,s -graphic

The split graph K _r + $\overline {{K_s}} $ on r+s vertices is denoted by S _r,s . A non-increasing sequence π = (d ₁, d ₂, …, d _n ) of nonnegative integers is said to be potentially S _r,s -graphic if there exists a realization of π containing S _r,s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S _r,s -graphic. They are extensions of two theorems due to A.R.Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series 4 (1979), 251–267 and An Erd?s-Gallai type result on the clique number of a realization of a degree sequence, unpublished).     

Degree sequences of graphs containing a cycle with prescribed length

Let r ≥ 3, n ≥ r and π = (d ₁, d ₂, ..., d _n ) be a non-increasing sequence of nonnegative integers. If π has a realization G with vertex set V (G) = {v ₁, v ₂, ..., v _n } such that d _G (v _i ) = d _i for i = 1, 2, ..., n and v ₁ v ₂ ... v _r v ₁ is a cycle of length r in G, then π is said to be potentially C _r ″-graphic. In this paper, we give a characterization for π to be potentially C _r ″-graphic. This work was supported by the grant of National Natural Science Foundation of China No. 10861006 and China Scholarship Council.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

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.     

A characterization for a graphic sequence to be potentially C r -graphic

Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-graphic for r 3 and n r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely.     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

A Rao-type characterization for a sequence to have a realization containing a split graph

For a given graph H, a non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. The split graph on r+s vertices is denoted by S_r,s. In this paper, we give a Rao-type characterization for π to be potentially S_r,s-graphic. A simplification of this characterization is also presented.     

Complementary ℓ1-Graphs Embeddable in the Half-Cube

A finite connected graph is called an ℓ₁-graph if it can be isometrically embedded into the space ℓ₁. We complete the classification of pairs of complementaryℓ₁ -graphs started by Deza and Huang, and continued by Shpectorov.     

Highly connected multicoloured subgraphs of multicoloured graphs

Suppose the edges of the complete graph on n vertices, E(K_n), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4, that if r=2s+1 then the answer lies between and , and that phase transitions occur at s=r/2 and . We shall also mention some of the more glaring open problems relating to this question.     

Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

A d-graph is a complete graph whose edges are colored by d colors, that is, partitioned into d subsets some of which might be empty. We say that a d-graph is complementary connected (CC) if the complement to each chromatic component of is connected on V. We prove that every such d-graph contains a sub-d-graph Π or , where Π has four vertices and two non-empty chromatic components each of which is a P₄, while is a three-colored triangle. This statement implies that each Π- and -free d-graph is uniquely decomposable in accordance with a tree whose leaves are the vertices of V and the interior vertices of T are labeled by the colors 1,…d. Such a tree is naturally interpreted as a positional game form (with perfect information and without moves of chance) of d players I={1,…,d} and n outcomes V={v₁,…,v_n}. Thus, we get a one-to-one correspondence between these game forms and Π- and -free d-graphs. As a corollary, we obtain a characterization of the normal forms of positional games with perfect information and, in case d=2, several characterizations of the read-once Boolean functions. These results are not new; in fact, they are 30 and, in case d=2, even 40 years old. Yet, some important proofs did not appear in English.Gyárfás and Simonyi recently proved a similar decomposition theorem for the -free d-graphs. They showed that each -free d-graph can be obtained from the d-graphs with only two non-empty chromatic components by successive substitutions. This theorem is based on results by Gallai, Lovász, Cameron and Edmonds. We obtain some new applications of these results.     

Amply regular graphs and block designs

We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ₃(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.     

On unavoidable hypergraphs

A r-uniform hypergraph H (or a r-graph, for short) is a collection E = E(H) of r-element subsets (called edges) of a set V = V(H) (called vertices). We say a r-graph H is (n, e)-unavoidable if every r-graph with n vertices and e edges must contain H. In this paper we investigate the largest possible number of edges in an (n, e)-unavoidable 3-graph for fixed n and e. We also study the structure of such unavoidable 3-graphs.     

Distance-regular Graphs of the Height h

The height of a distance-regular graph of the diameter d is defined by h=max{j|p ^d _d,j≠0}. We show that if Γ is a distance-regular graph of diameter d, height h>1 and every p ^d _d,h-graph is a clique, then h∈{d−1,d}. Revised: November 30, 1998     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

有一个实现包含Kr +1的可图序列

设K _{r +1}是一个r +1个顶点的完全图. 一个可图序列π =(d₁, d₂,…, d_n)称为是蕴含K _r+1 -可图的, 如果π有一个实现包含 K _{r +1}作为子图. 该文进一步研究了蕴含K _{r+1 -}可图序列的一些新的条件, 证明了这些条件包含文献[14,10,11]中的一些主要结果和当n≥5r/2 +1时,σ(K _r+1, n)之值(此值在文献[2]中被猜测, 在文献[6,7,8,3]中被证实). 此外, 确定了所有满足n≥5, d₅≥4 且不蕴含K₅ -可图序列π=(d₁, d₂,…, d_n)的集合.     

Minimal regular 2-graphs and applications

A 2-graph is a hypergraph with edge sizes of at most two. A regular 2-graph is said to be minimal if it does not contain a proper regular factor. Let f2(n) be the maximum value of degrees over all minimal regular 2-graphs of n vertices. In this paper, we provide a structure property of minimal regular 2-graphs, and consequently, prove that f2(n) = n 3-i/3, where 1 ≤ i ≤ 6, i ≡ n (mod 6) and n ≥ 7, which solves a conjecture posed by Fan, Liu, Wu and Wong. As applications in graph theory, we are able to characterize unfactorable regular graphs and provide the best possible factor existence theorem on degree conditions. Moreover, fa(n) and the minimal 2-graphs can be used in the universal switch box designs, which originally motivated this study.     

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).