On Trees with Double Domination Number Equal to the 2-Outer-Independent Domination Number Plus One

A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.     

Total Chromatic Number of the Join of K_(m,n) and C_n

The total chromatic number XT(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if XT(G)=Δ(G) 1. In this paper we prove that the join of a complete bipartite graph Km,n and a cycle Cn is of Type 1.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs

The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of black vertices(whereas vertices in V(G)\S are colored white)such that V(G)is turned black after finitely many applications of"the color-change rule":a white vertex is converted black if it is the only white neighbor of a black vertex.We show that dim(T)≤Z(T)for a tree T,and that dim(G)≤Z(G)+1 if G is a unicyclic graph;along the way,we characterize trees T attaining dim(T)=Z(T).For a general graph G,we introduce the"cycle rank conjecture".We conclude with a proof of dim(T)-2≤dim(T+e)≤dim(T)+1 for e∈E(T).     

Ladder图和Mbius Ladder图的彩虹点连通数（英文）

A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a rainbow u-v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G) ≤ srvc(G) for any nontrivial connected graph G. In this paper, for a Ladder L_n,we determine the exact value of srvc(L_n) for n even. For n odd, upper and lower bounds of srvc(L_n) are obtained. We also give upper and lower bounds of the(strong) rainbow vertex-connection number of Mbius Ladder.     

Rainb ow Vertex-connection Numb er of Ladder and M¨obius Ladder

A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a rainbow u-v geodesic, then G is strong rainbow vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of G, denoted by srvc(G). Observe that rvc(G) ≤ srvc(G) for any nontrivial connected graph G. In this paper, for a Ladder Ln, we determine the exact value of srvc(Ln) for n even. For n odd, upper and lower bounds of srvc(Ln) are obtained. We also give upper and lower bounds of the (strong) rainbow vertex-connection number of M¨obius Ladder.     

Planar graphs with maximum degree 8 and without intersecting chordal 4-cycles are 9-totally colorable

The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ’’ (G). It is shown that if a planar graph G has maximum degree Δ≥9, then χ’’ (G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ ’’(G) = 9.     

On the Ratio Between 2-Domination and Total Outer-Independent Domination Numbers of Trees

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D.A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D,and the set V(G)\D is independent.The 2-domination(total outer-independent domination,respectively)number of a graph G is the minimum cardinality of a 2-dominating(total outer-independent dominating,respectively)set of G.We investigate the ratio between2-domination and total outer-independent domination numbers of trees.     

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained.     

本刊英文版Vol.27(2011),No.9论文摘要(英文)

<正>Graphs Whose Critical Groups Have Larger Rank Yao Ping HOU Wai Chee SHIU Wai Hong CHAN Abstract The critical group C(G) of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix.Let r(G) be the minimum number of generators(i.e.,the rank) of the group C(G) andβ(G) be the number of independent     

Constructive characterizations of (γp,γ)- and (γp,γpr)-trees

Let G = (V,E) be a graph without isolated vertices.A set S V is a domination set of G if every vertex in V - S is adjacent to a vertex in S,that is N[S] = V.The domination number of G,denoted by γ(G),is the minimum cardinality of a domination set of G.A set S C V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching.The paired-domination number,denoted by γpr(G),is defined to be the minimum cardinality of a paired-domination set S in G.A subset S V is a power domination set of G if all vertices of V can be observed recursively by the following rules: (i) all vertices in N[S] are observed initially,and (ii) if an observed vertex u has all neighbors observed except one neighbor v,then v is observed (by u).The power domination number,denoted by γp(G),is the minimum cardinality of a power domination set of G.In this paper,the constructive characterizations for trees with γp = γ and γpr = γp are provided respectively.     

完全二部图K_(8,n)的点可区别IE-全染色（英文）

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)~(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.     

Constructive characterizations of （γp, γ）- and （γp, γpr）-trees

Let G =(V,E) be a graph without isolated vertices.A set S  V is a domination set of G if every vertex in V -S is adjacent to a vertex in S,that is N[S] = V .The domination number of G,denoted by γ(G),is the minimum cardinality of a domination set of G.A set S  V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S]has a perfect matching.The paired-domination number,denoted by γpr(G),is defined to be the minimum cardinality of a paired-domination set S in G.A subset S  V is a power domination set of G if all vertices of V can be observed recursively by the following rules:(i) all vertices in N[S] are observed initially,and(ii) if an observed vertex u has all neighbors observed except one neighbor v,then v is observed(by u).The power domination number,denoted by γp(G),is the minimum cardinality of a power domination set of G.In this paper,the constructive characterizations for trees with γp = γ and γpr = γp are provided respectively.     

Bounds on the clique-transversal number of regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.     

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K_(7,n) when 7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C(x) denote the set of colors of vertex x and of the edges incident with x, we call C(x) the color set of x. If C(u)≠ C(v) for any two different vertices u and v of V(G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by χ_(vt)~e(G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K_(7,n)(7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K_(7,n)(7 ≤ n ≤ 95) has been obtained.     

Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs K4,n and Kn,n

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

关于完全二部图$K_{4, n}$和$K_{n, n}$的点可区别 $IE$-全染色的一些注记

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

外平面图的邻点可区别Ⅰ-全染色（英文）

Let G be a simple graph with no isolated edge. An Ⅰ-total coloring of a graph G is a mapping φ : V(G) ∪ E(G) → {1, 2, ···, k} such that no adjacent vertices receive the same color and no adjacent edges receive the same color. An Ⅰ-total coloring of a graph G is said to be adjacent vertex distinguishing if for any pair of adjacent vertices u and v of G, we have C_φ(u) = C_φ(v), where C_φ(u) denotes the set of colors of u and its incident edges. The minimum number of colors required for an adjacent vertex distinguishing Ⅰ-total coloring of G is called the adjacent vertex distinguishing Ⅰ-total chromatic number, denoted by χ_at~i(G).In this paper, we characterize the adjacent vertex distinguishing Ⅰ-total chromatic number of outerplanar graphs.     

Embedding Cartesian Product of Some Graphs in Books

The book embedding of a graph G consists of placing the vertices of G in a line called spine and assigning edges of the graph to pages so that the edges assigned to the same page do not intersect. The number of pages is the minimum number in which the graph can be embedded. In this paper, we study the book embedding of the Cartesian product Pm × Sn, Pm × Wn, Cn × Sm, Cn × Wm, and get an upper bound of their pagenumber.