The minimum span of L(2,1)-labelings of certain generalized Petersen graphs

In the classical channel assignment problem, transmitters that are sufficiently close together are assigned transmission frequencies that differ by prescribed amounts, with the goal of minimizing the span of frequencies required. This problem can be modeled through the use of an L(2,1)-labeling, which is a function f from the vertex set of a graph G to the non-negative integers such that |f(x)-f(y)|? 2 if xand y are adjacent vertices and |f(x)-f(y)|?1 if xand y are at distance two. The goal is to determine the λ-number of G, which is defined as the minimum span over all L(2,1)-labelings of G, or equivalently, the smallest number k such that G has an L(2,1)-labeling using integers from {0,1,…,k}. Recent work has focused on determining the λ-number of generalized Petersen graphs (GPGs) of order n. This paper provides exact values for the λ-numbers of GPGs of orders 5, 7, and 8, closing all remaining open cases for orders at most 8. It is also shown that there are no GPGs of order 4, 5, 8, or 11 with λ-number exactly equal to the known lower bound of 5, however, a construction is provided to obtain examples of GPGs with λ-number 5 for all other orders. This paper also provides an upper bound for the number of distinct isomorphism classes for GPGs of any given order. Finally, the exact values for the λ-number of n-stars, a subclass of the GPGs inspired by the classical Petersen graph, are also determined. These generalized stars have a useful representation on Möebius strips, which is fundamental in verifying our results.     

L（1, 2）-edge-labelings for lattices

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, 1, 2,..., m}, such that adjacent edges which receive labels differ at least by j, and edges which are distance two apart receive labels differ at least by kThe λ j,k-number of G is the minimum m such that an m-L(j, k)-edge-labeling is admitted by GIn this article, the L(1, 2)-edge-labeling for the hexagonal lattice, the square lattice and the triangular lattice are studied, and the bounds for λ j,k-numbers of these graphs are obtained.     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

Labeling planar graphs with a condition at distance two

An L(2,1)-labeling of a graph is a mapping c:V(G)→{0,…,K} such that the labels assigned to neighboring vertices differ by at least 2 and the labels of vertices at distance two are different. The smallest K for which an L(2,1)-labeling of a graph G exists is denoted by λ_2,1(G). Griggs and Yeh [J.R. Griggs, R.K. Yeh, Labeling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595] conjectured that λ_2,1(G)≤Δ² for every graph G with maximum degree Δ≥2. We prove the conjecture for planar graphs with maximum degree Δ≠3. All our results also generalize to the list-coloring setting.     

On island sequences of labelings with a condition at distance two

An L(2,1)-labeling of a graph G is a function f from the vertex set of G to the set of nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1, and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between the pair of vertices x,y. The lambda number of G, denoted λ(G), is the minimum range of labels used over all L(2,1)-labelings of G. An L(2,1)-labeling of G which achieves the range λ(G) is referred to as a λ-labeling. A hole of an L(2,1)-labeling is an unused integer within the range of integers used. The hole index of G, denoted ρ(G), is the minimum number of holes taken over all its λ-labelings. An island of a given λ-labeling of G with ρ(G) holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] inquired about the existence of a connected graph G with ρ(G)≥1 possessing two λ-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2.     

Labelling of some planar graphs with a condition at distance two

The problem of vertex labeling with a condition at distance two in a graph, is a variation of Hale’s channel assignment problem, which was first explored by Griggs and Yeh. For positive integerp ≥q, the λ _p,q -number of graph G, denoted λ(G;p, q), is the smallest span among all integer labellings ofV(G) such that vertices at distance two receive labels which differ by at leastq and adjacent vertices receive labels which differ by at leastp. Van den Heuvel and McGuinness have proved that λ(G;p, q) ≤ (4q-2) Δ+10p+38q-24 for any planar graphG with maximum degree Δ. In this paper, we studied the upper bound of λ _p ,q-number of some planar graphs. It is proved that λ(G;p, q) ≤ (2q?1)Δ + 2(2p?1) ifG is an outerplanar graph and λ(G;p,q) ≤ (2q?1) Δ + 6p - 4q - 1 if G is a Halin graph.     

Labeling trees with a condition at distance two

An L(h,k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h,k)-labeling is the difference between the largest and the smallest label. We investigate L(h,k)-labelings of trees of maximum degree Δ, seeking those with small span. Given Δ, h and k, span λ is optimal for the class of trees of maximum degree Δ, if λ is the smallest integer such that every tree of maximum degree Δ has an L(h,k)-labeling with span at most λ. For all parameters Δ,h,k, such that h<k, we construct L(h,k)-labelings with optimal span. We also establish optimal span of L(h,k)-labelings for stars of arbitrary degree and all values of h and k.     

On spectral characterizations and embeddings of graphs

The least eigenvalue of the 0-1 adjacency matrix of a graph is denoted λ G. In this paper all graphs with λ(G) greater than ?2 are characterized. Such a graph is a generalized line graph of the form L(T;1,0,…,0), L(T), L(H), where T is a tree and H is unicyclic with an odd cycle, or is one of 573 graphs that arise from the root system E₈. If G is regular with λ(G)>?2, then Gis a clique or an odd circuit. These characterizations are used for embedding problems; λ_R(H) = sup{λ(G)z.sfnc;HinG; Gregular}. H is an odd circuit, a path, or a complete graph iff λ_R(H)> ?2. For any other line graph H, λ_R(H) = ?2. A similar result holds for complete multipartite graphs.     

An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|?2 when d_G(u,v)=1 and |f(u)-f(v)|?1 when d_G(u,v)=2. The L(2,1)-labelling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2,1)-labelling. The hole index ρ(G) of G is the minimum number of integers not used in a λ(G)-L(2,1)-labelling of G. We say G is full-colorable if ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2m and ρ(G)=m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].     

Perfect k-line graphs and k-total graphs

The concept of the line graph can be generalized as follows. The k-line graph L_k(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L_k(G) if and only if they have in G k ? 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3-line graphs and 3-total graphs. Moreover, perfect 3-line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Hamiltonian cycles in generalized petersen graphs

Watkins (J. Combinatorial Theory 6 (1969), 152–164) introduced the concept of generalized Petersen graphs and conjectured that all but the original Petersen graph have a Tait coloring. Castagna and Prins (Pacific J. Math. 40 (1972), 53–58) showed that the conjecture was true and conjectured that generalized Petersen graphs G(n, k) are Hamiltonian unless isomorphic to G(n, 2) where n ≡ 5(mod 6). The purpose of this paper is to prove the conjecture of Castagna and Prins in the case of coprime numbers n and k.     

The structure of even factors in claw-free graphs

Recently, Jackson and Yoshimoto proved that every bridgeless simple graph G with δ(G)≥3 has an even factor in which every component has order at least four, which strengthens a classical result of Petersen. In this paper, we give a strengthening of the above result and show that the above graphs have an even factor in which every component has order at least four that does not contain any given edge. We also extend the above result to the graphs with minimum degree at least three such that all bridges lie in a common path and to the bridgeless graphs that have at most two vertices of degree two respectively. Finally we use this extended result to show that every simple claw-free graph G of order n with δ(G)≥3 has an even factor with at most components. The upper bound is best possible.     

Distance-biregular graphs with 2-valent vertices and distance-regular line graphs

A graph G is called distance-regularized if each vertex of G admits an intersection array. It is known that every distance-regularized graph is either distance-regular (DR) or distance-biregular (DBR). Note that DBR means that the graph is bipartite and the vertices in the same color class have the same intersection array. A (k, g)-graph is a k-regular graph with girth g and with the minimum possible number of vertices consistent with these properties. Biggs proved that, if the line graph L(G) is distance-transitive, then G is either K_1,n or a (k, g)-graph. This result is generalized to DR graphs by showing that the following are equivalent: (1) L(G) is DR and G ≠ K_1,n for n ≥ 2, (2) G and L(G) are both DR, (3) subdivision graph S(G) is DBR, and (4) G is a (k, g)-graph. This result is used to show that a graph S is a DBR graph with 2-valent vertices iff S = K_2,′ or S is the subdivision graph of a (k, g)-graph. Let G⁽²⁾ be the graph with vertex set that of G and two vertices adjacent if at distance two in G. It is shown that for a DBR graph G, G⁽²⁾ is two DR graphs. It is proved that a DR graph H without triangles can be obtained as a component of G⁽²⁾ if and only if it is a (k, g)-graph with g ≥ 4.     

Strong edge-magic graphs of maximum size

An edge-magic total labeling on G is a one-to-one map λ from V(G)∪E(G) onto the integers 1,2,…,|V(G)∪E(G)| with the property that, given any edge (x,y), λ(x)+λ(x,y)+λ(y)=k for some constant k. The labeling is strong if all the smallest labels are assigned to the vertices. Enomoto et al. proved that a graph admitting a strong labeling can have at most 2|V(G)|-3 edges. In this paper we study graphs of this maximum size.     

On the harmonious coloring of collections of graphs

The hermonious coloring number of the graph G, HC(G), is the smallest number of colors needed to label the vertices of G such that adjacent vertices received different colors and no two edges are incident with the same color pair. In this paper, we investigate the HC-number of collections of disjoint paths, cycles, complete graphs, and complete bipartite graphs. We determine exact expressions for the HC-number of collections of paths and 4m-cycles. © 1995, John Wiley & Sons, Inc.     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

Queue layouts of iterated line directed graphs

In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph.We present upper and lower bounds on the queuenumber of an iterated line directed graph L^k(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of L^k(G), it is shown that for any fixed directed graph G, L^k(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in L^k(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.     

Clique partitions of distance multigraphs

We consider the minimum number of cliques needed to partition the edge set of D(G), the distance multigraph of a simple graph G. Equivalently, we seek to minimize the number of elements needed to label the vertices of a simple graph G by sets so that the distance between two vertices equals the cardinality of the intersection of their labels. We use a fractional analogue of this parameter to find lower bounds for the distance multigraphs of various classes of graphs. Some of the bounds are shown to be exact.     

Linear choosability of graphs

A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L-list colorable if for a given list assignment L={L(v):v∈V(G)}, there exists a linear coloring c of G such that c(v)∈L(v) for all v∈V(G). If G is linearly L-list colorable for any list assignment with |L(v)|?k for all v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem.