Search

An acyclic colouring of a graph is a proper colouring of the graph, for which every cycle uses at least three colours. In this paper, we describe a method for constructing all 4-connected acyclically 4-colourable planar triangulations that have exactly four odd-vertices, except the ones that contain no adjacent odd-vertices. Unlike previous operations, our method successfully establishes a connection with (acyclic) 4-colourings. Moreover, we discuss a special class of graphs, called diamond triangulations, and give a necessary and sufficient condition for a diamond triangulation to be acyclically 4-colourable. [ABSTRACT FROM AUTHOR]

Given a positive integer t and a graph F, the goal is to assign a subset of the color set { 1 , 2 , ... , t } to every vertex of F such that every vertex with the empty set assigned has all t colors in its neighborhood. Such an assignment is called the t-rainbow dominating function ( t RDF ) of the graph F. A t RDF is independent ( I t RDF ) if vertices assigned with non-empty sets are pairwise non-adjacent. The weight of a t RDF g of a graph F is the value w (g) = ∑ v ∈ V (F) | g (v) | . The independent t-rainbow domination number i r t (F) is the minimum weight over all I t RDF s of F. In this article, it is proved that the independent t-rainbow domination problem is NP-complete even if the input graph is restricted to a bipartite graph or a planar graph, and the results of the study provide some bounds for the independent t-rainbow domination number of any graph for a positive integer t. Moreover, the exact values and bounds of the independent t-rainbow domination numbers of some Petersen graphs and torus graphs are given. [ABSTRACT FROM AUTHOR]

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]

For a graph $$G=(V, E)$$ , a weak $$\{2\}$$ -dominating function $$f:V\rightarrow \{0,1,2\}$$ has the property that $$\sum _{u\in N(v)}f(u)\ge 2$$ for every vertex $$v\in V$$ with $$f(v)= 0$$ , where N( v) is the set of neighbors of v in G. The weight of a weak $$\{2\}$$ -dominating function f is the sum $$\sum _{v\in V}f(v)$$ and the minimum weight of a weak $$\{2\}$$ -dominating function is the weak $$\{2\}$$ -domination number. In this paper, we introduce a discharging approach and provide a short proof for the lower bound of the weak $$\{2\}$$ -domination number of $$C_n \Box C_5$$ , which was obtained by Stȩpień, et al. (Discrete Appl Math 170:113-116, 2014). Moreover, we obtain the weak $$\{2\}$$ -domination numbers of $$C_n \Box C_3$$ and $$C_n \Box C_4$$ . [ABSTRACT FROM AUTHOR]

Let $$G=(V, E)$$ be a graph. Denote $$d_G(u, v)$$ the distance between two vertices u and v in G. An L(2, 1)-labeling of G is a function $$f: V \rightarrow \{0,1,\ldots \}$$ such that for any two vertices u and v, $$|f(u)-f(v)| \ge 2$$ if $$d_G(u, v) = 1$$ and $$|f(u)-f(v)| \ge 1$$ if $$d_G(u, v) = 2$$ . The span of f is the difference between the largest and the smallest number in f( V). The $$\lambda $$ -number $$\lambda (G)$$ of G is the minimum span over all L(2, 1)-labelings of G. In this paper, we conclude that the $$\lambda $$ -number of each brick product graph is 5 or 6, which confirms Conjecture 6.1 stated in Li et al. (J Comb Optim 25:716-736, 2013). [ABSTRACT FROM AUTHOR]

The semitotal domination number of a graph G without isolated vertices is the minimum cardinality of a set S of vertices of G such that every vertex in $$V(G){\setminus } S$$ is adjacent to at least one vertex in S, and every vertex in S is within distance 2 of another vertex of S. In Henning and Marcon (Ann Comb 20(4):1-15, 2016), it was shown that every connected claw-free cubic graph G of order n has semitotal domination number at most $$\frac{4n}{11}$$ when $$n\ge 10$$ , and it was conjectured that the bound can be improved from $$\frac{4n}{11}$$ to $$\frac{n}{3}$$ if $$G\notin \{K_4,N_2\}$$ . In this paper, we prove this conjecture. [ABSTRACT FROM AUTHOR]

The frequency assignment problem (FAP) asks for assigning frequencies (channels) in a wireless network from the available radio spectrum to the transceivers of the network. One of the graph theoretical models of FAP is the L(3, 2, 1)-labeling of a graph, which is an abstraction of assigning integer frequencies to radio transceivers such that (i) transceivers that are one unit of distance apart receive frequencies that differ by at least three, (ii) transceivers that are two units of distance apart receive frequencies that differ by at least two, and (iii) transceivers that are three units of distance apart receive frequencies that differ by at least one. The relaxation of the L(3, 2, 1)-labeling called the ( s, t, r)-relaxed k- L(3, 2, 1)-labeling is proposed in this paper. This concept is a generalization of the ( s, t)-relaxed k- L(2, 1)-labeling (Lin in J Comb Optim 2016, doi:). Basic properties of ( s, t, r)-relaxed k- L(3, 2, 1)-labeling are discussed and optimal ( s, t, r)-relaxed k- L(3, 2, 1)-labelings for paths and some cycles as well as for the hexagonal lattice and the square lattice are determined. [ABSTRACT FROM AUTHOR]

A graphGis uniquelyk-colourable if the chromatic number ofGiskandGhas only onek-colouring up to permutation of the colours. Aksionov [On uniquely 3-colorable planar graphs, Discrete Math. 20 (1977), pp. 209–216] conjectured that every uniquely 3-colourable planar graph with at least four vertices has two adjacent triangles. However, in the same year, Melnikov and Steinberg [L.S. Mel'nikov and R. Steinberg,One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977), pp. 203–206.] disproved the conjecture by constructing a counterexample. In this paper, we prove that if a uniquely 3-colourable planar graphGhas at most 4 triangles thenGhas two adjacent triangles. Furthermore, for any, we construct a uniquely 3-colourable planar graph withktriangles and without adjacent triangles. [ABSTRACT FROM PUBLISHER]

Let $$G=(V, E)$$ be a graph. Denote $$d_G(u, v)$$ the distance between two vertices $$u$$ and $$v$$ in $$G$$ . An $$L(2, 1)$$ -labeling of $$G$$ is a function $$f: V \rightarrow \{0,1,\cdots \}$$ such that for any two vertices $$u$$ and $$v$$ , $$|f(u)-f(v)| \ge 2$$ if $$d_G(u, v) = 1$$ and $$|f(u)-f(v)| \ge 1$$ if $$d_G(u, v) = 2$$ . The span of $$f$$ is the difference between the largest and the smallest number in $$f(V)$$ . The $$\lambda $$ -number of $$G$$ , denoted $$\lambda (G)$$ , is the minimum span over all $$L(2,1 )$$ -labelings of $$G$$ . In this article, we confirm Conjecture 6.1 stated in X. Li et al. (J Comb Optim 25:716-736, ) in the case when (i) $$\ell $$ is even, or (ii) $$\ell \ge 5$$ is odd and $$0 \le r \le 8$$ . [ABSTRACT FROM AUTHOR]

An acyclic $$k$$ -coloring of a graph $$G$$ is a $$k$$ -coloring of its vertices such that no cycle of $$G$$ is bichromatic. $$G$$ is called acyclically $$k$$ -colorable if it admits an acyclic $$k$$ -coloring. In this paper, we prove that the generalized Petersen graph $$P(n,k)$$ is acyclically 3-colorable except $$P(4,1)$$ and the classical Petersen graph $$P(5,2)$$ . [ABSTRACT FROM AUTHOR]