An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference betw...An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.展开更多
<span style="font-family:Verdana;">This note is considered as a sequel of Yeh [<a href="#ref1">1</a>]. Here, we present a generalized (vertex) distance labeling (labeling vertices...<span style="font-family:Verdana;">This note is considered as a sequel of Yeh [<a href="#ref1">1</a>]. Here, we present a generalized (vertex) distance labeling (labeling vertices under constraints depending the on distance between vertices) of a graph. Instead of assigning a number (label) to each vertex, we assign a set of numbers to each vertex under given conditions. Some basic results are given in the first part of the note. Then we study a particular class of this type of labelings on several classes of graphs.</span>展开更多
This paper shows that, for every unit interval graph, there is a labelling which is simultaneously optimal for the following seven graph labelling problems: bandwidth, cyclic bandwidth, profile, fill-in, cutwidth, mod...This paper shows that, for every unit interval graph, there is a labelling which is simultaneously optimal for the following seven graph labelling problems: bandwidth, cyclic bandwidth, profile, fill-in, cutwidth, modified cutwidth, and bandwidth sum(linear arrangement).展开更多
A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this pape...A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.展开更多
A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct...A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct. In fact, it is a Hopf algebra since it is graded connected. The main conclusions are that the vector space spanned by labeled simple graphs arising from the unshuffle coproduct is a Hopf algebra and that there is a Hopf homomorphism from permutations to label simple graphs.展开更多
In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admi...In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admits a Zero-M-Cordial labeling. Further we prove that Kn × P2Bn = K1,n × P2 of odd n admits a Zero-M-Cordial labeling.展开更多
The design of large disk array architectures leads to interesting combinatorial problems. Minimizing the number of disk operations when writing to consecutive disks leads to the concept of “cluttered orderings” whic...The design of large disk array architectures leads to interesting combinatorial problems. Minimizing the number of disk operations when writing to consecutive disks leads to the concept of “cluttered orderings” which were introduced for the complete graph by Cohen et al. (2001). Mueller et al. (2005) adapted the concept of wrapped Δ-labellings to the complete bipartite case. In this paper, we give some sequence in order to generate wrapped Δ-labellings as cluttered orderings for the complete bipartite graph. New sequence we give is different from the sequences Mueller et al. gave, though the same graphs in which these sequences are labeled.展开更多
L(2,1)-labeling number of the product and the join graph on two fans are discussed in this paper, we proved that L(2,1)-labeling number of the product graph on two fans is?λ(G) ≤ Δ+3 , L(2,1)-labeling number of the...L(2,1)-labeling number of the product and the join graph on two fans are discussed in this paper, we proved that L(2,1)-labeling number of the product graph on two fans is?λ(G) ≤ Δ+3 , L(2,1)-labeling number of the join graph on two fans is?λ(G) ≤ 2Δ+3.展开更多
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.展开更多
For a graph having no isolated vertex, a function is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is suc...For a graph having no isolated vertex, a function is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is such that the number of edges with label 0 and the number of edges with label 1 differ by at most 1 and the number of vertices with label 0 and the number of vertices with label 1 also differ by at most 1. In this paper, we discuss edge product cordial labeling for some cycle related graphs.展开更多
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.展开更多
An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u...An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.展开更多
The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact valu...The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel展开更多
Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bound...Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.展开更多
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.展开更多
Building up graph models to simulate scale-free networks is an important method since graphs have been used in researching scale-free networks. One use labelled graphs for distinguishing objects of communication and i...Building up graph models to simulate scale-free networks is an important method since graphs have been used in researching scale-free networks. One use labelled graphs for distinguishing objects of communication and information networks. In this paper some methods are given for constructing larger felicitous graphs from smaller graphs having special felicitous labellings, and some network models are shown to be felicitous.展开更多
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.展开更多
文摘An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.
文摘<span style="font-family:Verdana;">This note is considered as a sequel of Yeh [<a href="#ref1">1</a>]. Here, we present a generalized (vertex) distance labeling (labeling vertices under constraints depending the on distance between vertices) of a graph. Instead of assigning a number (label) to each vertex, we assign a set of numbers to each vertex under given conditions. Some basic results are given in the first part of the note. Then we study a particular class of this type of labelings on several classes of graphs.</span>
文摘This paper shows that, for every unit interval graph, there is a labelling which is simultaneously optimal for the following seven graph labelling problems: bandwidth, cyclic bandwidth, profile, fill-in, cutwidth, modified cutwidth, and bandwidth sum(linear arrangement).
文摘A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.
文摘A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct. In fact, it is a Hopf algebra since it is graded connected. The main conclusions are that the vector space spanned by labeled simple graphs arising from the unshuffle coproduct is a Hopf algebra and that there is a Hopf homomorphism from permutations to label simple graphs.
文摘In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admits a Zero-M-Cordial labeling. Further we prove that Kn × P2Bn = K1,n × P2 of odd n admits a Zero-M-Cordial labeling.
文摘The design of large disk array architectures leads to interesting combinatorial problems. Minimizing the number of disk operations when writing to consecutive disks leads to the concept of “cluttered orderings” which were introduced for the complete graph by Cohen et al. (2001). Mueller et al. (2005) adapted the concept of wrapped Δ-labellings to the complete bipartite case. In this paper, we give some sequence in order to generate wrapped Δ-labellings as cluttered orderings for the complete bipartite graph. New sequence we give is different from the sequences Mueller et al. gave, though the same graphs in which these sequences are labeled.
文摘L(2,1)-labeling number of the product and the join graph on two fans are discussed in this paper, we proved that L(2,1)-labeling number of the product graph on two fans is?λ(G) ≤ Δ+3 , L(2,1)-labeling number of the join graph on two fans is?λ(G) ≤ 2Δ+3.
文摘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.
文摘For a graph having no isolated vertex, a function is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is such that the number of edges with label 0 and the number of edges with label 1 differ by at most 1 and the number of vertices with label 0 and the number of vertices with label 1 also differ by at most 1. In this paper, we discuss edge product cordial labeling for some cycle related graphs.
文摘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.
基金The NSF (60673048) of China the NSF (KJ2009B002,KJ2009B237Z) of Education Ministry of Anhui Province.
文摘An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.
基金Supported by the National Natural Science Foundation of China (1 0 0 71 0 76 )
文摘The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel
文摘Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.
文摘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.
文摘Building up graph models to simulate scale-free networks is an important method since graphs have been used in researching scale-free networks. One use labelled graphs for distinguishing objects of communication and information networks. In this paper some methods are given for constructing larger felicitous graphs from smaller graphs having special felicitous labellings, and some network models are shown to be felicitous.
基金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.
