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.     

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

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.     

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.     

Graphic Sequences with a Realization Containing a Union of Cliques

An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = K_m1∪ K_m2∪...∪ K_mk when n is a sufficiently large integer. This is accomplished by determining σ(K_j + kK₂,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ m_i.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Conditions for -graphic sequences to be potentially -graphic

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 said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-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].     

A Variation of an Extremal Theorem Due to Woodall

We consider a variation of an extremal theorem due to Woodall [12, or 1, Chapter 3] as follows: Determine the smallest even integer (₃C₁,n), such that every n-term graphic sequence = (d₁, d₂,..., d_n) with term sum () = d₁ + d₂ + ... + d_n (₃C₁,n) has a realization G containing a cycle of length r for each r = 3,4,...,l. In this paper, the values of (₃C_l,n) are determined for l = 2m – 1,n 3m – 4 and for l = 2m,n 5m – 7, where m 4.AMS Mathematics subject classification (1991) 05C35Project supported by the National Natural Science Foundation of China (Grant No. 19971086) and the Doctoral Program Foundation of National Education Department of China     

Some results on the majorization theorem of connected graphs

Let π = (d ₁, d ₂, ..., d _n ) and π′ = (d′ ₁, d′ ₂, ..., d′ _n ) be two non-increasing degree sequences. We say π is majorizated by π′, denoted by π ⊲ π′, if and only if π ≠ π′, Σ _i=1 ⁿ d _i = Σ _i=1 ⁿ d′ _i , and Σ _i=1 ^j d _i ≤ Σ _i=1 ^j d′ _i for all j = 1, 2, ..., n. Weuse C _π to denote the class of connected graphs with degree sequence π. Let ρ(G) be the spectral radius, i.e., the largest eigenvalue of the adjacent matrix of G. In this paper, we extend the main results of [Liu, M. H., Liu, B. L., You, Z. F.: The majorization theorem of connected graphs. Linear Algebra Appl., 431(1), 553–557 (2009)] and [Bıyıkoğlu, T., Leydold, J.: Graphs with given degree sequence and maximal spectral radius. Electron. J. Combin., 15(1), R119 (2008)]. Moreover, we prove that if π and π′ are two different non-increasing degree sequences of unicyclic graphs with π ⊲ π′, G and G′ are the unicyclic graphs with the greatest spectral radii in C _π and C′ _π , respectively, then ρ(G) < ρ(G′).     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

Compound Poisson Approximation for Multiple Runs in a Markov Chain

We consider a sequence X ₁, ..., X _n of r.v.'s generated by a stationary Markov chain with state space A = {0, 1, ..., r}, r 1. We study the overlapping appearances of runs of k _i consecutive i's, for all i = 1, ..., r, in the sequence X ₁,..., X _n. We prove that the number of overlapping appearances of the above multiple runs can be approximated by a Compound Poisson r.v. with compounding distribution a mixture of geometric distributions. As an application of the previous result, we introduce a specific Multiple-failure mode reliability system with Markov dependent components, and provide lower and upper bounds for the reliability of the system.     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

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.     

Potentially <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> — <Emphasis Type="Italic">G</Emphasis>-graphical sequences: A survey

The set of all non-increasing nonnegative integer sequences π = (d(v ₁), d(v ₂), …, d(v _n )) is denoted by NS _n . A sequence π ∈ NS _n is 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 NS _n is denoted by GS _n . 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. Let K _k denote a complete graph on k vertices. Let K _m −H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of K _m ). This paper summarizes briefly some recent results on potentially K _m −G-graphic sequences and give a useful classification for determining σ (H, n).     

The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,G _k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G ₁), d(e, G ₂),…,d(e, G _k )), where d(e, G _i ) is the distance from e to G _i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K _n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999     

Nonexistence of sparse triple systems over abelian groups and involutions

In 1973 Paul Erdős conjectured that there is an integer v ₀(r) such that, for every v>v ₀(r) and v≡1,3 (mod 6), there exists a Steiner triple system of order v, containing no i blocks on i+2 points for every 1<i≤r. Such an STS is said to be r-sparse. In this paper we consider relations of automorphisms of an STS to its sparseness. We show that for every r≥13 there exists no point-transitive r-sparse STS over an abelian group. This bound and the classification of transitive groups give further nonexistence results on block-transitive, flag-transitive, 2-transitive, and 2-homogeneous STSs with high sparseness. We also give stronger bounds on the sparseness of STSs having some particular automorphisms with small groups. As a corollary of these results, it is shown that various well-known automorphisms, such as cyclic, 1-rotational over arbitrary groups, and involutions, prevent an STS from being high-sparse.      

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity