Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

On the sum of the reciprocals of cycle lengths in sparse graphs

For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal [1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)⁻¹ for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths.     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

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.     

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

CLASSIFICATION OF COMPLETE 5-PARTITE GRAPHS AND CHROMATICITY OF 5-PARTITE GRAPHSWITH 5n VERTICES

For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained.     

Highly linked graphs

A graph with at least 2k vertices is said to bek-linked if, for any choices ₁,...,s _k ,t ₁,...,t _k of 2k distinct vertices there are vertex disjoint pathsP ₁,...,P _k withP _i joinings _i tot _i , 1ik. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds . We show here thatk(G)22k will do.     

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.     

Chromatic uniqueness of certain complete tripartite graphs

Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k ²/4 + i + 1.     

AF-Embedding of Crossed Products of Certain Graph C＊-algebras by Quasi-free Actions （II）

Let E be a row-finite directed graph, let G be a locally compact abelian group with dual group Ĝ = Γ, let ω be a labeling map from E* to Γ, and let (C*(E), G, α ^ω ) be the C*-dynamical system defined by ω. Some mappings concerning the AF-embedding construction of C*(E) ×_a^w GC*(E) \times _{\alpha ^\omega } G are studied in more detail. Several necessary conditions of AF-embedding and some properties of almost proper labeling map are obtained. Moreover it is proved that if E is constructed by attaching some 1-loops to a directed graph T consisting of some rooted directed trees and G is compact, then ω is almost proper, that is a sufficient condition for AF-embedding, if and only if Σ _j=1 ^k w_gj 1 1_G\omega _{\gamma _j } \ne 1_\Gamma for any loop γ _i , γ ₂, ..., γ _k attached to one path in T.     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

Arc-disjoint in-trees in directed graphs

Given a directed graph D = (V,A) with a set of d specified vertices S = {s ₁,…, s _d } ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ _i=1 ^d f(s _i ) arc-disjoint in-trees denoted by T _i,1,T _i,2,…, for every i = 1,…,d such that T _i,1,…, are rooted at s _i and each T _i,j spans the vertices from which s _i is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case. Supported by JSPS Research Fellowships for Young Scientists. Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan.     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Total domination in claw-free graphs with minimum degree 2

A set S of vertices in a graph G is a total dominating set (TDS) of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). A graph is claw-free if it does not contain K_1,3 as an induced subgraph. It is known [M.A. Henning, Graphs with large total domination number, J. Graph Theory 35(1) (2000) 21-45] that if G is a connected graph of order n with minimum degree at least two and G∉{C₃,C₅, C₆, C₁₀}, then γ_t(G)?4n/7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γ_t(G)?(n+2)/2 and we characterize those graphs for which γ_t(G)=⌊(n+2)/2⌋.     

A Construction of Uniquely C4-free colourable Graphs

Abstract

An F-free colouring of a graph G is a partition {V₁,V₂,…,V_n} of the vertex set V(G) of G such that F is not an induced subgraph of G[V_i] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C₄-free colourable graphs exist.