The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. ...The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.展开更多
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...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.展开更多
A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two d...A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.展开更多
Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination numb...Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.展开更多
A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set ...A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].展开更多
In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex v<sub>i</sub> in a simple graph G, in terms of the ad...In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex v<sub>i</sub> in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.展开更多
Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing probl...Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.展开更多
The present paper deals with the gracefulness of unconnected graph （jC_（4n））∪P_m,and proves the following result：for positive integers n,j and m with n≥1,j≥2,the unconnected graph（jC_（4n））∪P_m is a gracef...The present paper deals with the gracefulness of unconnected graph （jC_（4n））∪P_m,and proves the following result：for positive integers n,j and m with n≥1,j≥2,the unconnected graph（jC_（4n））∪P_m is a graceful graph for m=j-1 or m≥n＋j,where C_（4n） is a cycle with 4n vertexes,P_m is a path with m＋1 vertexes,and（jC_（4n））∪P_m denotes the disjoint union of j-C_（4n） and P_m.展开更多
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.展开更多
Ewa·Wojcicka [1] has proved that the connected 3 γ critical graphs has a H path and has put forward to such a conjecture: Connected 3 γ critical graphs without endpoints are H graphs. In this paper,we prove tha...Ewa·Wojcicka [1] has proved that the connected 3 γ critical graphs has a H path and has put forward to such a conjecture: Connected 3 γ critical graphs without endpoints are H graphs. In this paper,we prove that if G is a connected 3 γ critical graph without endpoints and has a H paht ap →a such that d(a,b)=3, then G is a H graph. The result partially solves Ewa. Wojcickas conjecture.展开更多
For positive numbers j and k, an L（j,k）-labeling f of G is an assignment of numbers to vertices of G such that ｜f（u）-f（v）｜≥j if uv∈E（G）, and ｜f（u）-f（v）｜≥k if d（u,v）=2. Then the span of f is the di...For positive numbers j and k, an L（j,k）-labeling f of G is an assignment of numbers to vertices of G such that ｜f（u）-f（v）｜≥j if uv∈E（G）, and ｜f（u）-f（v）｜≥k if d（u,v）=2. Then the span of f is the difference between the maximum and the minimum numbers assigned by f. The L（j,k）-number of G, denoted by λj,k（G）, is the minimum span over all L（j,k）-labelings of G. In this paper, we give some results about the L（j,k）-number of the direct product of a path and a cycle for j≤k.展开更多
An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called ...An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called the independence polynomial of G(Gutman and Harary,1983).In this paper,we introduce a new graph operation called the cycle cover product and formulate its independence polynomial.We also give a criterion for formulating the independence polynomial of a graph.Based on the exact formulas,we prove some results on symmetry,unimodality,reality of zeros of independence polynomials of some graphs.As applications,we give some new constructions for graphs having symmetric and unimodal independence polynomials.展开更多
文摘The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.
基金Supported in part by the NNSF of China(10301010,60673048)Science and Technology Commission of Shanghai Municipality(04JC14031).
文摘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.
文摘A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.
文摘Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.
文摘A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].
文摘In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex v<sub>i</sub> in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.
文摘Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.
文摘The present paper deals with the gracefulness of unconnected graph （jC_（4n））∪P_m,and proves the following result：for positive integers n,j and m with n≥1,j≥2,the unconnected graph（jC_（4n））∪P_m is a graceful graph for m=j-1 or m≥n＋j,where C_（4n） is a cycle with 4n vertexes,P_m is a path with m＋1 vertexes,and（jC_（4n））∪P_m denotes the disjoint union of j-C_（4n） and P_m.
文摘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.
文摘Ewa·Wojcicka [1] has proved that the connected 3 γ critical graphs has a H path and has put forward to such a conjecture: Connected 3 γ critical graphs without endpoints are H graphs. In this paper,we prove that if G is a connected 3 γ critical graph without endpoints and has a H paht ap →a such that d(a,b)=3, then G is a H graph. The result partially solves Ewa. Wojcickas conjecture.
基金Supported by Faculty Research Grant, Hong Kong Baptist University
文摘For positive numbers j and k, an L（j,k）-labeling f of G is an assignment of numbers to vertices of G such that ｜f（u）-f（v）｜≥j if uv∈E（G）, and ｜f（u）-f（v）｜≥k if d（u,v）=2. Then the span of f is the difference between the maximum and the minimum numbers assigned by f. The L（j,k）-number of G, denoted by λj,k（G）, is the minimum span over all L（j,k）-labelings of G. In this paper, we give some results about the L（j,k）-number of the direct product of a path and a cycle for j≤k.
基金Supported by National Natural Science Foundation of China(Grant Nos.11971206,12022105)Natural Science Foundation for Distinguished Young Scholars of Jiangsu Province(Grant No.BK20200048)。
文摘An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called the independence polynomial of G(Gutman and Harary,1983).In this paper,we introduce a new graph operation called the cycle cover product and formulate its independence polynomial.We also give a criterion for formulating the independence polynomial of a graph.Based on the exact formulas,we prove some results on symmetry,unimodality,reality of zeros of independence polynomials of some graphs.As applications,we give some new constructions for graphs having symmetric and unimodal independence polynomials.
