$$L(p,q)$$ L ( p, q ) -labeling and integer tension of a graph embedded on torus

Xiaoling L. Zhang and Jianguo G. Qian ()
Additional contact information
Xiaoling L. Zhang: Xiamen University
Jianguo G. Qian: Xiamen University

Journal of Combinatorial Optimization, 2016, vol. 31, issue 1, No 6, 67-77

Abstract: Abstract The $$L(p, q)$$ L ( p , q ) -labeling arises from the optimization problem of channel assignment in communication networks. For two non-negative integers $$p$$ p and $$q$$ q , an $$L(p,q)$$ L ( p , q ) -labeling $$c$$ c of a graph $$G$$ G is an assignment of non-negative integers to the vertices of $$G$$ G such that adjacent vertices are labelled using colors at least $$p$$ p apart, and vertices with distance two are labelled using colors at least $$q$$ q apart. In this paper we establish a connection between an $$L(p, q)$$ L ( p , q ) -labeling and an integer tension of a graph, which extends a corresponding result for planar graphs. This connection provides us with an effective way to design an $$L(p, q)$$ L ( p , q ) -labeling for non-planar graphs, in particular for graphs embedded on torus, by choosing a proper cycle basis consisting of facial cycles and some specified cycles of the embedded graph. As an application, we use this method to optimize the edge span for the Cartesian product of two cycles.

Keywords: L(p; q)-labeling; Edge span; Tension; Graph embedded on torus; 05C12; 05C15; 68R10 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9714-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:1:d:10.1007_s10878-014-9714-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9714-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().