ON THE NORMALIZED LAPLACIAN SPECTRUM OF A NEW JOIN OF TWO GRAPHS

Given graphs G_1 and G_2, we define a graph operation on G_1 and G_2,namely the SSG-vertex join of G_1 and G_2, denoted by G_1 G_2. Let S(G) be the subdivision graph of G. The SSG-vertex join G_1G_2 is the graph obtained from S(G_1) and S(G_2) by joining each vertex of G_1 with each vertex of G_2. In this paper, when G_i(i = 1, 2) is a regular graph, we determine the normalized Laplacian spectrum of G_1 G_2. As applications, we construct many pairs of normalized Laplacian cospectral graphs, the normalized Laplacian energy, and the degree Kirchhoff index of G_1G_2.     

Graphs with vertex rainbow connection number two

An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.     

An implicit degree ore-condition for pancyclicity of graphs

In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id(v). In this paper, we prove that if G is a 2-connected graph of order n such that id(u) + id(v) ≥ n for each pair of nonadjacent vertices u and v in G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is isomorphic to F4r .     

Vertex Distinguishing Equitable Total Chromatic Number of Join Graph

A vertex distinguishing equitable total coloring of graph G is a proper total coloring of graph G such that any two distinct vertices＇ coloring sets are not identical and the difference of the elements colored by any two colors is not more than 1. In this paper we shall give vertex distinguishing equitable total chromatic number of join graphs Pn VPn, Cn VCn and prove that they satisfy conjecture 3, namely, the chromatic numbers of vertex distinguishing total and vertex distinguishing equitable total are the same for join graphs Pn V Pn and Cn ∨ Cn.     

Nordhaus-Gaddum results for the sum of the induced path number of a graph and its complement

The induced path number ρ(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path.Broere et al.proved that if G is a graph of order n,then n~(1/2) ≤ρ(G) + ρ(■) ≤ [3n/2].In this paper,we characterize the graphs G for which ρ(G) + ρ(■) = [3n/2],improve the lower bound on ρ(G) + ρ(■) by one when n is the square of an odd integer,and determine a best possible upper bound for ρ(G) + ρ(■) when neither G nor ■ has isolated vertices.     

Longest Cycles in 3-Connected, K_(1,3)-Free Graphs

The graph considered in this paper is an undireeted graph of order n,without loops alld multiple edges.Denotea by V(G)the vertex set of graph G,by |V(G)| the cardinality of V(G),by K(G)the connectivity of G,by δ the minimum degree of G.A eyele in G is considered as a Subgraph of G,and for a Subgraph H of G.1et G-H denote the Subgraph of G inducedby vertex set V(G)-y(日).M. M.Marthews and D.P.Summer proved in 1986 that eVery 2-eonneeted, K_1,3-free     

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.     

Unique factorization of compositive hereditary graph properties

A graph property is any class of graphs that is closed under isomorphisms. A graph property P is hereditary if it is closed under taking subgraphs; it is compositive if for any graphs G1, G2 ∈ P there exists a graph G ∈ P containing both G1 and G2 as subgraphs. Let H be any given graph on vertices v1, . . . , vn, n ≥ 2. A graph property P is H-factorizable over the class of graph properties P if there exist P 1 , . . . , P n ∈ P such that P consists of all graphs whose vertex sets can be partitioned into n parts, possibly empty, satisfying: 1. for each i, the graph induced by the i-th non-empty partition part is in P i , and 2. for each i and j with i = j, there is no edge between the i-th and j-th parts if vi and vj are non-adjacent vertices in H. If a graph property P is H-factorizable over P and we know the graph properties P 1 , . . . , P n , then we write P = H [ P 1 , . . . , P n ]. In such a case, the presentation H[ P 1 , . . . , P n ] is called a factorization of P over P. This concept generalizes graph homomorphisms and (P 1 , . . . , P n )-colorings. In this paper, we investigate all H-factorizations of a graph property P over the class of all hered- itary compositive graph properties for finite graphs H. It is shown that in many cases there is exactly one such factorization.     

On the number of matchings of graphs formed by a graph operation

Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a,b) of G and by joining each new vertex e* to the end vertices a and b of the edge e corresponding to it. In this paper, we prove that the number of matchings of R(G) is completely determined by the degree sequence of vertices of G.     

On strong metric dimension of graphs and their complements

A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices S■V(G) is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim(G), is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim(G) equals 1, n-1, or n-2, respectively. We give a Nordhaus-Gaddum-type result for the strong metric dimension of a graph and its complement: for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim(G)+sdim(G)≤2( n-2). It is readily seen that sdim(G)+sdim(G)=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim(G)+sdim(G)=2(n 2) if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim(G)+sdim(G)≤2(n-3) if G is a tree; we also show that 4≤sdim(G)+sdim(G)≤2(n-3) if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim(G)+sdim(G)=2(n-3) when G is a tree or a unicyclic graph.     

$K_{2,3}$的剖分图与$P_n, C_n$的联图交叉数

在完全图$K_{2,3}$的任意一边增加一个新的顶点, 则得到$K_{2,3}$的一个剖分图(六阶图). 本文研究得到了这个特殊六阶图与$n$个孤立点$nK_1$, 路$P_n$, 圈$C_n$的联图交叉数.     

无$K_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

关于完全二部图$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.     

偶图$K_{n,n+7}-A(|A|\leq3)$的圈长分布唯一性

阶为$n$的图$G$的圈长分布是序列($c_1,c_2,\ldots,c_n$), 其中$c_i$是图$G$中长为$i$的圈数.本文得到如下结果: 设$A\subseteq E(K_{n,n+7})$,在以下情况, 图 $G$ 由其圈长分布唯一确定.(1) $G=K_{n,n+7}$(n\geq10)$;(2) $G=K_{n,n+7}-A$ $(|A|=1,n\geq12)$;(3)$G=K_{n,n+7}-A$(|A|=2,n\geq14)$;(4)$G=K_{n,n+7}-A$ $(|A|=3     

由圈长分布确定的二部图~$K_{n,n r}-A\ (|A|\leq 3)$

The cycle length distribution of a graph G of order n is a sequence （c1 （G）,…, cn （G））, where ci （G） is the number of cycles of length i in G. In general, the graphs with cycle length distribution （c1（G） ,…,cn（G）） are not unique. A graph G is determined by its cycle length distribution if the graph with cycle length distribution （c1 （G）,…, cn （G）） is unique. Let Kn,n＋r be a complete bipartite graph and A lohtaib in E（Kn,n＋r）. In this paper, we obtain： Let s 〉 1 be an integer. （1） If r = 2s, n 〉 s（s - 1） ＋ 2｜A｜, then Kn,n＋r - A （A lohtain in E（Kn,n＋r）,｜A｜ ≤ 3） is determined by its cycle length distribution; （2） If r = 2s ＋ 1,n 〉 s^2 ＋ 2｜A｜, Kn,n＋r - A （A lohtain in E（Kn,n＋r）, ｜A｜ ≤3） is determined by its cycle length distribution.     

环状硅酸盐图的友好指数集

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f : V(G) →Z2 induces an edge labeling f*: E(G) → Z2 defined by f*(xy) = f(x) + f(y), for each edge xy ∈ E(G). For i ∈ Z2, let vf(i) = |{v ∈ V(G) : f(v) = i}| and ef(i) = |{e ∈ E(G) : f*(e) =i}|. A labeling f of a graph G is said to be friendly if |vf(0)- vf(1)| ≤ 1. The friendly index set of the graph G, denoted FI(G), is defined as {|ef(0)- ef(1)|: the vertex labeling f is friendly}. This is a generalization of graph cordiality. We investigate the friendly index sets of cyclic silicates CS(n, m).     

$K_{5}\times S_{n}$ 的交叉数

把完全图$K_{5}$的五个顶点与另外$n$个顶点都联边得到一类特殊的图$H_{n}$.文中证明了$H_{n}$的交叉数为$Z(5,n)+2n+\lfloor \frac{n}{2}\rfloor+1$,并在此基础上证明了$K_{5}$与星$K_{1,n}$的笛卡尔积的交叉数为$Z(5,n)+5n+\lfloor\frac{n}{2} \rfloor+1$.     

单圈图的极小能量

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un| d(x) = r for any vertex x ∈ V(Cl)}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39(2, 2, 2) ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.     

2-连通半无爪图的最长圈

A graph G is called quasi-claw-free if it satisfies the property:d(x,y)=2 there exists a vertex u∈N(x)∩N(y)such that N[u]■N[x]∪N[y].In this paper,we show that every 2-connected quasi-claw-free graph of order n with G■F contains a cycle of length at least min{3δ+2,n},where F is a family of graphs.     

图$(\bigcup\limits_{i{\in}A}P_i){\bigcup}(\bigcup\limits_{j{\in}B}U_j)$伴随唯一的充要条件

设$h(G; x) =h(G)$和$[G]_h$分别表示图$G$的伴随多项式和伴随等价类. 文中给出了$[G]_h$的一个新应用. 利用$[G]_h$, 给出了图$H{\;}(H \cong G)$伴随唯一的充要条件, 其中$H=(\bigcup_{i{\in}A}P_i){\bigcup}(\bigcup_{j{\in}B}U_j)$, $A \subseteq A^{'}=\{1,2,3,5\} \bigcup \{2n|n \in N, n \geq 3\}$, $B \subseteq B^{'}