RADIO NUMBER OF kth POWER OF A PATH
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let G be a connected graph. For any two vertices u and v, let d(u, v) denote the distance between u and v in G. The maximum distance between any pair of vertices is called the diameter of G and is denoted by diam(G). A radio labeling of a connected graph G is an assignment of distinct positive integers to the vertices of G, with v ∈ V (G) labeled by f(v), such that |f(u)-f(v)|+d(u, v) ≥ 1+diam(G) holds for all u, v ∈ V , u ≠ v. The radio number rn(f) of a radio labeling f of G is the maximum label assigned by f to a vertex of G. The radio number rn(G) of G is the minfrn(f)g over all radio labeling f of G. The kth power of a graph G, denoted by Gk, is the graph on the vertices of G with two vertices u and v are adjacent in Gk whenever d(u, v) ≤ k in G. In this paper, we completely determine the radio number of the graph Pk n for positive integers n, k with k ≥ 2.
Abstract
Let G be a connected graph. For any two vertices u and v, let d(u, v) denote the distance between u and v in G. The maximum distance between any pair of vertices is called the diameter of G and is denoted by diam(G). A radio labeling of a connected graph G is an assignment of distinct positive integers to the vertices of G, with v ∈ V (G) labeled by f(v), such that |f(u)-f(v)|+d(u, v) ≥ 1+diam(G) holds for all u, v ∈ V , u ≠ v. The radio number rn(f) of a radio labeling f of G is the maximum label assigned by f to a vertex of G. The radio number rn(G) of G is the minfrn(f)g over all radio labeling f of G. The kth power of a graph G, denoted by Gk, is the graph on the vertices of G with two vertices u and v are adjacent in Gk whenever d(u, v) ≤ k in G. In this paper, we completely determine the radio number of the graph Pk n for positive integers n, k with k ≥ 2.
참고문헌 (15)
- Buckley F, "Distance in Graphs" (1990), Addison-Wesley
- P. Devadas Rao, "Radio labeling of fourth power of a path", International Journal of Combinatorial Graph Theory and Applications, 3(2), pp.81~103 (2010)
- G. Chartrand, "Radio labelings of graphs", Bull. Inst. Combin. Appl., 33, pp.77~85 (2001)
- Gary Chartrand, "A graph labeling problem Suggested by FM Channel Restrictions", Bulletin of the Inst. Combin. Appl., 43, pp.43~57 (2005)
- W. K. Hale, "Frequency assignment : Theory and applications", Proc. IEEE, 68, pp.11971511~ (1980)
- D.D.F. Liu, "Radio number for square of cycles", congr, Numer., 169, pp.105~125 (2004)
- D.D.F. Liu, "Radio number of square paths", Ars Comb., 90, pp.307~319 (2009)
- D.D. F. Liu, "Multilevel Distance Labelings for paths and cycles", SIAM J. Discrete Math., 19, pp.610~621 (2005)[DOI]
- J. A. Gallian, "A dynamic survey of graph labeling", The Electronic Journal of Combinatorics, DS6, pp.1~219 (2009)
- Hartsfield Gerhard, "Pearls in Graph Theory" (1994), Academic Press
- B. Sooryanarayana, "Radio labeling of cube of a cycle", Far East J. Appl. Math, 29(1), pp.113~147 (2007)
- B. Sooryanarayana, "Radio labeling of <TEX>$C_n^4$<", TEX>, 2007, pp.3(2), 195~228
- B. Sooryanarayana, "Radio labeling of cube of a Path", International J. Math. Comb., 1, pp.5~29 (2010)
- J.Van den Heuvel, "Graph labeling and radio Channel Assignment", J.Graph Theory, 29, pp.263~283 (1998)[DOI]
- P.Zhang, "Radio labellings of Cycles", Ars Combin., 65, pp.21~32 (2002)