A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for ...A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.展开更多
In the paper, we study the gracefulness of several unconnected graphs related to wheel. For natural number p ≥ 1, t ≥ 1 , let n = 2t ＋ 3,2t ＋ 4 , which proved W. U K （1） p,t U K（2） is graceful; for p≥1, t≥1 ...In the paper, we study the gracefulness of several unconnected graphs related to wheel. For natural number p ≥ 1, t ≥ 1 , let n = 2t ＋ 3,2t ＋ 4 , which proved W. U K （1） p,t U K（2） is graceful; for p≥1, t≥1 ,let n=2t＋3,2t＋4, then Wn,2n＋1 U K（1）p,t U K（2） p,t is graceful and for m ≥ 1, r ≥ 1 , let n = 2m ＋ 5, Wn,2n＋1 U （C3 v Km） U St（r） is graceful.展开更多
A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges c...A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges can be colored by assigning a different color to each of its edges. The edge coloring is appropriate if adjacent edges are given different colors. In this work, we introduce a new labeling called NK-labeling. Let c:E(G)→ℕbe a proper edge coloring of G which induces a proper vertex coloring c′:V(G)→ℤndefined by c′(v)≡∑e∈Evc(e)modnSuch that Evis the set of edges incident with vin G. The minimum positive integer for which the graph G has NK-labeling called NK-chromatic index and denoted by χ′NK(G). We study the NK-labeling of several well-known classes of graphs. It is shown that the NK-chromatic of the path Pnfor n≥4is three and for odd n, the NK-chromatic of the complete graph Knis n. Other results dealing with the NK-labeling are also presented.展开更多
The Q-index of a graph G is the largest eigenvalue q（G） of its signless Laplacian matrix Q（G）. In this paper, we prove that the wheel graph W_n = K_1 ∨C_（n-1）is the unique graph with maximal Q-index among all H...The Q-index of a graph G is the largest eigenvalue q（G） of its signless Laplacian matrix Q（G）. In this paper, we prove that the wheel graph W_n = K_1 ∨C_（n-1）is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.展开更多
We introduce Tribonacci cordial labeling as an extension of Fibonacci cordial labeling, a well-known form of vertex-labelings. A graph that admits Tribonacci cordial labeling is called Tribonacci cordial graph. In thi...We introduce Tribonacci cordial labeling as an extension of Fibonacci cordial labeling, a well-known form of vertex-labelings. A graph that admits Tribonacci cordial labeling is called Tribonacci cordial graph. In this paper we investigate whether some well-known graphs are Tribonacci cordial.展开更多
For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which ...For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.展开更多
A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x ,y) is in E for each x not equal to y . The motivation to study representable gr...A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x ,y) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.展开更多
基金The NSF(11271365)of Chinathe NSF(BK20151117)of Jiangsu Province
文摘A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.
基金Supported by the Natural Science Foundation of Beijing(1102015)University Scientific Research Project of Hebei Province(Z2014032)the Fundamental Research Funds for the Central Universities(HKXJZD201402,2011B019,3142013025,3142014127)
文摘In the paper, we study the gracefulness of several unconnected graphs related to wheel. For natural number p ≥ 1, t ≥ 1 , let n = 2t ＋ 3,2t ＋ 4 , which proved W. U K （1） p,t U K（2） is graceful; for p≥1, t≥1 ,let n=2t＋3,2t＋4, then Wn,2n＋1 U K（1）p,t U K（2） p,t is graceful and for m ≥ 1, r ≥ 1 , let n = 2m ＋ 5, Wn,2n＋1 U （C3 v Km） U St（r） is graceful.
文摘A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges can be colored by assigning a different color to each of its edges. The edge coloring is appropriate if adjacent edges are given different colors. In this work, we introduce a new labeling called NK-labeling. Let c:E(G)→ℕbe a proper edge coloring of G which induces a proper vertex coloring c′:V(G)→ℤndefined by c′(v)≡∑e∈Evc(e)modnSuch that Evis the set of edges incident with vin G. The minimum positive integer for which the graph G has NK-labeling called NK-chromatic index and denoted by χ′NK(G). We study the NK-labeling of several well-known classes of graphs. It is shown that the NK-chromatic of the path Pnfor n≥4is three and for odd n, the NK-chromatic of the complete graph Knis n. Other results dealing with the NK-labeling are also presented.
基金Supported by the National Natural Science Foundation of China(Grant No.11171273)the Seed Foundation of Innovation and Creation for Graduate Students in Northwestern Polytechnical University(Grant No.Z2016170)
文摘The Q-index of a graph G is the largest eigenvalue q（G） of its signless Laplacian matrix Q（G）. In this paper, we prove that the wheel graph W_n = K_1 ∨C_（n-1）is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.
文摘We introduce Tribonacci cordial labeling as an extension of Fibonacci cordial labeling, a well-known form of vertex-labelings. A graph that admits Tribonacci cordial labeling is called Tribonacci cordial graph. In this paper we investigate whether some well-known graphs are Tribonacci cordial.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1097102510901035)
文摘For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.
文摘A graph G=(V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x ,y) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.
