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｝ .展开更多
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.展开更多
Let G be a graph. The partially square graph G~* of G is a graph obtainedfrom G by adding edges uv satisfying the conditions uv E(G), and there is somew ∈N(u)∩N(v), such that N(w) N(u:)∪ N(v)∪ {u, v}. In this pape...Let G be a graph. The partially square graph G~* of G is a graph obtainedfrom G by adding edges uv satisfying the conditions uv E(G), and there is somew ∈N(u)∩N(v), such that N(w) N(u:)∪ N(v)∪ {u, v}. In this paper, we will use thetechnique of the vertex insertion on l-connected (l=k or k+1, k≥2) graphs to providea unified proof for G to be hamiltonian , 1-hamiltonian or hamiltonia11-connected. Thesufficient conditions are expresscd by the inequality concerning sum from i=1 to k |N(Y_i)| and n(Y) in Gfor each independent set Y={y_1, y_2,…,y_k} in G~*, where K_i= {y_i, y_(i-1),…,y_(i-(b-1)) }Y for i ∈{1, 2,…,k} (the subscriptions of y_j's will be taken modulo k), 6 (0 <b <k)is an integer,and n(Y) = |{v∈V(G): dist(v,Y) ≤2}|.展开更多
文摘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｝ .
文摘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.
基金Supported by National Natural Sciences Foundation of China(19971043)
文摘Let G be a graph. The partially square graph G~* of G is a graph obtainedfrom G by adding edges uv satisfying the conditions uv E(G), and there is somew ∈N(u)∩N(v), such that N(w) N(u:)∪ N(v)∪ {u, v}. In this paper, we will use thetechnique of the vertex insertion on l-connected (l=k or k+1, k≥2) graphs to providea unified proof for G to be hamiltonian , 1-hamiltonian or hamiltonia11-connected. Thesufficient conditions are expresscd by the inequality concerning sum from i=1 to k |N(Y_i)| and n(Y) in Gfor each independent set Y={y_1, y_2,…,y_k} in G~*, where K_i= {y_i, y_(i-1),…,y_(i-(b-1)) }Y for i ∈{1, 2,…,k} (the subscriptions of y_j's will be taken modulo k), 6 (0 <b <k)is an integer,and n(Y) = |{v∈V(G): dist(v,Y) ≤2}|.
