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.     

图G_n的优美表示

将给出三个结果:(i)如果图G是SZ(|S|=n≥2)上的整数和图,那么0∈S当且仅当图G至少有一个(n-1)度顶点;(ii)图G(G≠K2)是至少有两个零点的整数和图当且仅当G■K2·Gn;(iii)设图G(G≠K2)是SZ上的整数和图,|S|=n+2,n∈N+.若图G至少有两个零点,则S={mx|m=-1,0,1,2,…,n;x∈Z且x≠0}.     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

Threshold characterization of graphs with dilworth number two

A graph with nodes 1, …, n is a threshold signed graph if one can find two positive real numbers S, T and real numbers a₁, …, a_n associated with the vertices in such a way that i, j are linked iff either |a_i + a_j| ≥ S or |a_i - a_j| ≥ T. Such graphs generalize threshold graphs. It is shown that these graphs are precisely the graphs with Dilworth number at most two (the Dilworth number is the maximum number of pairwise incomparable vertices in the vicinal preorder). Some other properties of this subclass of perfect graphs are also presented. The graphs considered in this paper are finite simple graphs G = (V, E), where V is the vertex set of G and E a subset of pairs of G. For x V, N(x) denotes the neighbor set of x: N(x) = {y | {x, y} E}.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

GENERALISED MAXIMAL INDEPENDENCE AND CLIQUE NUMBERS OF GRAPHS

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let β_k, (G) (w_k(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously β_k(G) = w_k([Gbar]). For the sequence m₁ ? m₂ ?…? m_n = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that w_k(G) = m_k for k = 1,2,…,n and w(G) = r (equivalently, β_k(G) = m_k for k = 1,2,…,n and β(G) = r). Define s_k(?,m) to be the largest integer such that for every graph G with at most s_k(?,m) vertices, β_k(G) ? ? or w_k(G) ? m. Exact values for s_k(?,m) if k ≥ 2 and upper and lower bounds for s₁(?,m) are de termined.     

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009     

Hamiltonian decompositions of complete regular s-partite graphs

In this paper we give a procedure by which Hamiltonian decompositions of the s-partite graph K_n,n,…,n, where (s − 1)n is even, can be constructed. For 2t⩽s, 1⩽a₁⩽…⩽a_t⩽n, we find conditions which are necessary and sufficient for a decomposition of the edge-set of K_a1a2…,a_t into (s − 1)n/2 classes, each class consisting of disjoint paths, to be extendible to a Hamiltonian decomposition of the complete s-partite graph K_rmn,n,…,n so that each of the classes forms part of a Hamiltonian cycle.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界

对简单图G,|V(G)|=p,n是自然数,Mn(G)被称为图G的广义Mycielski图,如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}.文中针对简单图G与它的广义Mycielski图之间的关系,给出了G的广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界.     

关于P_(r,(2s-1))的奇优美标号

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2 |E|-1}满足1)对任意的u,v∈V,若u≠v,则(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4){g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇优美图,f称为G的奇优美标号.Gnanajoethi提出了一个猜想:每棵树都是奇优美的.证明了图P_(r,(2s-1)是奇优美图.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

Dominating sets with small clique covering number

Motivated by earlier work on dominating cliques, we show that if a graph G is connected and contains no induced subgraph isomorphic to P₆ or H_t (the graph obtained by subdividing each edge of K_1,t, t ≥ 3, by exactly one vertex), then G has a dominating set which induces a connected graph with clique covering number at most t − 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 101–105, 1997     

On 2-factors with cycles containing specified vertices in a bipartite graph

Let k≥1 be an integer and G=(V ₁,V ₂;E) a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+2. Our result is as follows: If $d(x)+d(y)\geq \lceil\frac{4n+k}{3}\rceil$ for any nonadjacent vertices x∈V ₁ and y∈V ₂, then for any k distinct vertices z ₁,…,z _k , G contains a 2-factor with k+1 cycles C ₁,…,C _k+1 such that z _i ∈V(C _i ) and l(C _i )=4 for each i∈{1,…,k}.     

可圈的一个充分条件

本文我们证明如下结果:设G=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

均衡二部图中含2k条指定边的k个独立圈及2-因子

得到了对于二部图G=(V_1,V_2;E),当|V_1|=|V_2|=n≥2k+1时的结果:对G中任意2k条独立边e_1,e_1~*,…,e_k,e_k~*,G中一定存在k个独立的4-圈C_1,C_2,…,C_k,使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i).并在此基础上进一步证明了当|V_1|=|V_2|=n≥3k时若对任意两顶点x∈V_1,y∈V_2,都有d(x)+d(y)≥2n-k+1成立,则G有一个2-因子含有k+1个独立圈C_1,C_2,…,C_(k+1)使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i)且|C_i|=4.     

On the number of increasing paths in labeled cycles and stars

A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.     

Hamiltonian graphs involving distances

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3K_n/3 U T₁ U T₂, where n ? O (mod 3), and T₁ and T₂ are the edge sets of two vertex disjoint triangles containing exactly one vertex from each K_n/3. This result generalizes both Fan's and Lindquester's results as well as several others.