The week's pick
Reseach Article
The L(2,1)-Labeling on γ-Product of Graphs and Improved Bound on the L(2,1)- Number of γ-Product of Graphs
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 128 - Number 11 |
| Year of Publication: 2015 |
| Authors: Anuj Kumar, P. Pradhan |
10.5120/ijca2015906676
|
Anuj Kumar, P. Pradhan . The L(2,1)-Labeling on γ-Product of Graphs and Improved Bound on the L(2,1)- Number of γ-Product of Graphs. International Journal of Computer Applications. 128, 11 ( October 2015), 40-45. DOI=10.5120/ijca2015906676
Abstract
The concept of L(2,1)-labeling in graph come into existence with the solution of frequency assignment problem. In fact, in this problem a frequency in the form of nonnegative integers is to assign to each radio or TV transmitters located at various places such that communication does not interfere. This frequency assignment problem can be modeled with vertex labeling of graphs. An L(2,1)-labeling (or distance two labeling) of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(u)−f(v)|≥2 if d(u,v)=1 and |f(u)−f(v)|≥1 if d(u,v)=2, where d(u,v) denotes the distance between u and v in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max {f(v):v ϵ V(G) }=k. In this paper, upper bound for the L(2,1)-labeling number for the γ-product of two graphs has been obtained in terms of the maximum degrees of the graphs involved and improved this bound by using a dramatically new approach on the analysis of the adjacency matrices of the graphs. By the new approach, we have achieved more accurate result with significant improvement of this bound.
References
- D.Gonccalves, On the L(p, 1) -labeling of graphs, in Proc. 2005 Eur. Conf. Combinatorics, Graph Theory Appl. S. Felsner, Ed., (2005), 81-86 .
- D. Kral and R. Skrekovski, A theorem about channel assignment problem, SIAM J. Discrete Math., 16 (2003) 426-437.
- D. D. F. Liu and R. K. Yeh, On Distance Two Labeling of Graphs, Ars Combinatoria, 47 (1997) 13-22.
- D. Sakai, Labeling Chordal Graphs with a condition at distance two, SIAM J. Discrete Math., 7 (1994) 133-140.
- D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of graphs-Theory and application, 2nd ed. New York: Academic, 1982.
- E. M. El-Kholy, E .S. Lashin and S. N. Daoud, New operations on graphs and graph foldings, International Mathematical Forum, 7(2012) 2253-2268.
- F. S .Roberts, “T-colorings of graphs; Recent results and open problems ,” Discr. Math. vol 93, pp. 229-245, 1991.
- G. J. Chang and D. Kuo, The L(2, 1) -labeling on graphs, SIAM J. Discrete Math., 9 (1996) 309-316.
- G. J. Chang and et al., On L(d, 1) -labeling of graphs, Discrete Math, 220 (2000) 57-66.
- J. R. Griggs and R. K. Yeh, Labeling graphs with a condition at distance two, SIAM J. Discrete Math., 5 (1992) 586-595.
- P. K. Jha, Optimal L(2, 1) -labeling of strong product of cycles, IEEE Trans. Circuits systems-I, Fundam. Theory Appl., 48(4) (2001) 498-500.
- P. K. Jha, Optimal L(2, 1) -labeling on Cartesian products of cycles with an application to independent domination, IEEE Trans. Circuits systems-I, Fundam. Theory Appl., 47(12) (2000) 1531-1534.
- P. Pradhan, K. Kumar, The L(2,1)-labeling on
Index Terms
Keywords