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 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.展开更多
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 G = (V, E) be a graph and C<sub>m</sub> be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm</sub>. An n-set distance lab...Let G = (V, E) be a graph and C<sub>m</sub> be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm</sub>. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ<sub>1</sub><sup>(n)</sup>(G). Basic results were presented in [1] for λ1</sub>(2)</sup>(C<sub>m</sub>) for all m and λ1</sub>(n)</sup>(C<sub>m</sub>) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1</sub>(n)</sup>(C<sub>m</sub>). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3 up to n = 500 by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.展开更多
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.展开更多
We present a new condition ensuring the existence of a large cycle of passing through given edge. Let l(C) denote the length of the cycle C. Suppose G is a 4-connected graph with vertices set {x1,X2, ···...We present a new condition ensuring the existence of a large cycle of passing through given edge. Let l(C) denote the length of the cycle C. Suppose G is a 4-connected graph with vertices set {x1,X2, ···,Xn} and edge set E and with the property that, for any two positive integers j and k,d(xj)【j+1,d(xk)【k(1)if j+k】n-1,then d(xj)+d(xk)】m;(2)if j+k【n-1,then d(xj)+d(xk)】min(k+3,m).In this paper, we proved that for any given edge e 6 E, there exists a cycle which passes through e abd with the length 】 min(m - 1, n).展开更多
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.展开更多
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.展开更多
基金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 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.
文摘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 G = (V, E) be a graph and C<sub>m</sub> be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm</sub>. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ<sub>1</sub><sup>(n)</sup>(G). Basic results were presented in [1] for λ1</sub>(2)</sup>(C<sub>m</sub>) for all m and λ1</sub>(n)</sup>(C<sub>m</sub>) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1</sub>(n)</sup>(C<sub>m</sub>). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3 up to n = 500 by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.
基金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.
文摘We present a new condition ensuring the existence of a large cycle of passing through given edge. Let l(C) denote the length of the cycle C. Suppose G is a 4-connected graph with vertices set {x1,X2, ···,Xn} and edge set E and with the property that, for any two positive integers j and k,d(xj)【j+1,d(xk)【k(1)if j+k】n-1,then d(xj)+d(xk)】m;(2)if j+k【n-1,then d(xj)+d(xk)】min(k+3,m).In this paper, we proved that for any given edge e 6 E, there exists a cycle which passes through e abd with the length 】 min(m - 1, n).
文摘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.
文摘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.
