Search

The frequency assignment problem (FAP) is the assignment of frequencies to television and radio transmitters subject to restrictions imposed by the distance between transmitters. One of the graph theoretical models of FAP which is well elaborated is the concept of distance constrained labeling of graphs. Let G = (V, E) be a graph. For two vertices u and v of G, we denote d(u, v) the distance between u and v. An L(2, 1)-labeling for G is a function f: V → {0, 1, · · · } such that |f (u) - f (v)| ≥ 1 if d(u, v) = 2 and |f (u) - f (v)| ≥ 2 if d(u, v) = 1. The span of f is the difference between the largest and the smallest number of f (V). The λ-number for G, denoted by λ(G), is the minimum span over all L(2, 1)-labelings of G. In this paper, we study the λ-number of the Cartesian and strong product of two directed cycles. We show that for m, n ≥ 4 the λ-number of -→ Cm2 - → Cn is between 4 and 5. We also establish the λ-number of - → C m - → C n for m ≤ 10 and prove that the λ-number of the strong product of cycles - → C m - → C n is between 6 and 8 for m, n ≥ 48. [ABSTRACT FROM AUTHOR]

The frequency assignment problem asks for assigning frequencies to transmitters in a wireless network and includes a variety of specific subproblems. In particular, the packing coloring problem comes from the regulations concerning the assignment of broadcast frequencies to radio stations. The problem is placed on a graph-theoretical footing and modeled as the packing chromatic number χ ρ ( G ) of a graph G . The packing chromatic number of G is the smallest integer k such that the vertex set V ( G ) can be partitioned into disjoint classes X 1 , … , X k , with the condition that vertices in X i have pairwise distance greater than i . The determination of the packing chromatic number is known to be NP -hard. This paper presents an integer linear programming model and a satisfiability test model for the packing coloring problem. The proposed models were applied for studying the packing chromatic numbers of Cartesian products of paths and cycles and for the packing chromatic numbers of some distance graphs. [ABSTRACT FROM AUTHOR]

A local colouring of a graphGis a functionc: V(G)→ℕ such that for eachS⊆V(G), 2≤|S|≤3, there existu, v∈Swith |c(u)−c(v)| at least the number of edges in the subgraph induced byS. The maximum colour assigned bycis the value χℓ(c) ofc, and the local chromatic number ofGis χℓ(G)=min {χℓ(c):cis a local colouring ofG}. In this note the local chromatic number is determined for Cartesian productsG □ H, whereGandGHare 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that ifGandHare graphs such that χ(G)≤⌊ χℓ(H)/2 ⌋, then χℓ(G □ H)≤χℓ(H)+1. [ABSTRACT FROM AUTHOR]

Abstract: The square of a graph is obtained from by adding edges joining all pairs of nodes at distance 2 in . In this note we prove that for . This confirms Conjecture 19 stated in [É. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327–2333]. [Copyright &y& Elsevier]

Let γ (D) denote the domination number of a digraph D and let C m □ C n denote the Cartesian product of C m and C n , the directed cycles of length n ≥ m ≥ 3 . Liu et al. obtained the exact values of γ (C m □ C n) for m up to 6 [Domination number of Cartesian products of directed cycles, Inform. Process. Lett. 111 (2010) 36–39]. Shao et al. determined the exact values of γ (C m □ C n) for m = 6 , 7 [On the domination number of Cartesian product of two directed cycles, Journal of Applied Mathematics, Volume 2013, Article ID 619695]. Mollard obtained the exact values of γ (C m □ C n) for m = 3 k + 2 [M. Mollard, On domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths, Discuss. Math. Graph Theory 33(2) (2013) 387–394.]. In this paper, we extend the current known results on C m □ C n with m up to 21. Moreover, the exact values of γ (C n □ C n) with n up to 31 are determined. [ABSTRACT FROM AUTHOR]