Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k...Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k+1, k≥2 ) claw-free graphs to provide a unified proof for G to be Hamiltonian, 1 -Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ k i=0N(Y i) and n(Y) in G for each independent set Y=｛y 0, y 1, …, y k｝ of the square graph of G , where b ( 0<b<k+1 ) is an integer, Y i=｛y i, y i-1, …, y i-(b-1)｝Y for i∈｛0, 1, …, k｝ , where subscriptions of y j s will be taken modulo k+1 , and n(Y)=｛v∈ V(G): dist (v, Y)≤ 2｝ .展开更多
Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we...Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we prove root square mean labeling of some degree splitting graphs.展开更多
A decomposition of a graph H is a partition of the edge set of H into edge-disjoint subgraphs . If for all , then G is a decomposition of H by G. Two decompositions and of the complete bipartite graph are orthogonal i...A decomposition of a graph H is a partition of the edge set of H into edge-disjoint subgraphs . If for all , then G is a decomposition of H by G. Two decompositions and of the complete bipartite graph are orthogonal if, for all . A set of decompositions of is a set of k mutually orthogonal graph squares (MOGS) if and are orthogonal for all and . For any bipartite graph G with n edges, denotes the maximum number k in a largest possible set of MOGS of by G. Our objective in this paper is to compute where is a path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an isomorphic to a certain graph F).展开更多
Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper...Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.展开更多
In this paper,for an arbitrary prime p,the square mapping graph of M2（Zp;s） is investigated and the formula of the decomposition of the square mapping graph of M2（Zp;s） is established.
A set ?is a dominating set of G if every vertex of ?is adjacent to at least one vertex of S. The cardinality of the smallest dominating set of G is called the domination number of G. The square G2 of a graph G is obta...A set ?is a dominating set of G if every vertex of ?is adjacent to at least one vertex of S. The cardinality of the smallest dominating set of G is called the domination number of G. The square G2 of a graph G is obtained from G by adding new edges between every two vertices having distance 2 in G. In this paper we study the domination number of square of graphs, find a bound for domination number of square of Cartesian product of cycles, and find the exact value for some of them.展开更多
In this paper we prove that the split graphs of K1,n and Bn,n are prime cordial graphs. We also show that the square graph of Bn,n is a prime cordial graph while middle graph of Pn is a prime cordial graph for n≥4 . ...In this paper we prove that the split graphs of K1,n and Bn,n are prime cordial graphs. We also show that the square graph of Bn,n is a prime cordial graph while middle graph of Pn is a prime cordial graph for n≥4 . Further we prove that the wheel graph Wn admits prime cordial labeling for n≥8.展开更多
In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.
文摘Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k+1, k≥2 ) claw-free graphs to provide a unified proof for G to be Hamiltonian, 1 -Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ k i=0N(Y i) and n(Y) in G for each independent set Y=｛y 0, y 1, …, y k｝ of the square graph of G , where b ( 0<b<k+1 ) is an integer, Y i=｛y i, y i-1, …, y i-(b-1)｝Y for i∈｛0, 1, …, k｝ , where subscriptions of y j s will be taken modulo k+1 , and n(Y)=｛v∈ V(G): dist (v, Y)≤ 2｝ .
文摘Let be an injective function. For a vertex labeling f, the induced edge labeling is defined by, or;then, the edge labels are distinct and are from . Then f is called a root square mean labeling of G. In this paper, we prove root square mean labeling of some degree splitting graphs.
文摘A decomposition of a graph H is a partition of the edge set of H into edge-disjoint subgraphs . If for all , then G is a decomposition of H by G. Two decompositions and of the complete bipartite graph are orthogonal if, for all . A set of decompositions of is a set of k mutually orthogonal graph squares (MOGS) if and are orthogonal for all and . For any bipartite graph G with n edges, denotes the maximum number k in a largest possible set of MOGS of by G. Our objective in this paper is to compute where is a path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an isomorphic to a certain graph F).
文摘Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.
基金This research was supported by the National Natural Science Foundation of Chin （11161006,11171142）,the Guangxi Natural Science Foundation（2011GXNSFA018139）and Guangx“New Century 1000 Talents Project”.
文摘In this paper,for an arbitrary prime p,the square mapping graph of M2（Zp;s） is investigated and the formula of the decomposition of the square mapping graph of M2（Zp;s） is established.
基金Supported by National Research Foundation of Singapore （NRF-CRP8-2011-03） and National Natural Science Foundation of China （61120106011, 61034007, 61203045, 61304045）
文摘A set ?is a dominating set of G if every vertex of ?is adjacent to at least one vertex of S. The cardinality of the smallest dominating set of G is called the domination number of G. The square G2 of a graph G is obtained from G by adding new edges between every two vertices having distance 2 in G. In this paper we study the domination number of square of graphs, find a bound for domination number of square of Cartesian product of cycles, and find the exact value for some of them.
文摘In this paper we prove that the split graphs of K1,n and Bn,n are prime cordial graphs. We also show that the square graph of Bn,n is a prime cordial graph while middle graph of Pn is a prime cordial graph for n≥4 . Further we prove that the wheel graph Wn admits prime cordial labeling for n≥8.
基金supported by National Natural Science Foundation of the People’s Republic of China“On the symmetries and local properties of graphs with square-free order”(11601005)Anhui Provincial Science Fund for Excellent Young Scholars“On the symmetries of edge-primitive graphs with square-free order”(gxyq2020011).
基金Supported by the National Natural Science Foundation of China(No.11271300)
文摘In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.
