Search

While a number of bounds are known on the zero forcing number Z(G) of a graph G expressed in terms of the order of a graph and maximum or minimum degree, we present two bounds that are related to the (upper) total domination number γ t (G) (resp. Γ t (G) ) of G. We prove that Z (G) + γ t (G) ≤ n (G) and Z (G) + Γ t (G) 2 ≤ n (G) holds for any graph G with no isolated vertices of order n(G). Both bounds are sharp as demonstrated by several infinite families of graphs. In particular, we show that every graph H is an induced subgraph of a graph G with Z (G) + Γ t (G) 2 = n (G) . Furthermore, we prove a characterization of graphs with power domination equal to 1, from which we derive a characterization of the extremal graphs attaining the trivial lower bound Z (G) ≥ δ (G) . The class of graphs that appears in the corresponding characterizations is obtained by extending an idea of Row for characterizing the graphs with zero forcing number equal to 2. [ABSTRACT FROM AUTHOR]

A sequence S of vertices of a graph G is called a dominating sequence of G if (1) each vertex v of S dominates a vertex of G that was not dominated by any of the vertices preceding vertex v in S, and (2) every vertex of G is dominated by at least one vertex of S. The Grundy Domination problem is to find a longest dominating sequence for a given graph G. It has been known that the decision version of the Grundy Domination problem is NP-complete even when restricted to chordal graphs. In this paper, we prove that the decision version of the Grundy Domination problem is NP-complete for bipartite graphs and co-bipartite graphs. On the positive side, we present a linear-time algorithm that solves the Grundy Domination problem for chain graphs, which form a subclass of bipartite graphs. [ABSTRACT FROM AUTHOR]

A set S of vertices of a graph G is a geodesic transversal of G if every maximal geodesic of G contains at least one vertex of S. We determine a smallest geodesic transversal in certain interconnection networks such as meshes of trees, and some well-known chemical structures such as silicate networks and carbon nanosheets. Some useful general bounds for the corresponding graph invariant are obtained along the way. [ABSTRACT FROM AUTHOR]

Given a finite graph G, the maximum length of a sequence (v 1 , ... , v k) of vertices in G such that each v i dominates a vertex that is not dominated by any vertex in { v 1 , ... , v i - 1 } is called the Grundy domination number, γ gr (G) , of G. A small modification of the definition yields the Z-Grundy domination number, which is the dual invariant of the well-known zero forcing number. In this paper, we prove that γ gr (G) ≥ n + ⌈ k 2 ⌉ - 2 k - 1 holds for every connected k-regular graph of order n different from K k + 1 and 2 C 4 ¯ . The bound in the case k = 3 reduces to γ gr (G) ≥ n 2 , and we characterize the connected cubic graphs with γ gr (G) = n 2 . If G is different from K 4 and K 3 , 3 , then n 2 is also an upper bound for the zero forcing number of a connected cubic graph, and we characterize the connected cubic graphs attaining this bound. [ABSTRACT FROM AUTHOR]

The study of a variation of the marking game, in which the first player marks vertices and the second player marks edges of an undirected graph was proposed by Bartnicki et al. (Electron J Combin 15:R72, 2008). In this game, the goal of the second player is to mark as many edges around an unmarked vertex as possible, while the first player wants just the opposite. In this paper, we prove various bounds for the corresponding graph invariant, the vertex-edge coloring number col ve (G) of a graph G. In particular, every (finite or infinite) graph G whose edges can be oriented in such a way that the maximum out-degree is bounded by an integer d has col ve (G) ≤ d + 2 . We investigate this invariant in (classes of) planar graphs, including some infinite lattices. We present a close connection between the vertex-edge coloring number of a graph G and the game coloring number of the subdivision graph S(G). In our main result, we bound the vertex-edge coloring number in complete graphs from below and from above, and while col ve (K n) ≤ ⌈ log 2 n ⌉ + 2 , the difference between the upper and the lower bound is roughly log 2 (log 2 n) . The latter results are, in fact, true for any multigraph whose underlying graph is K n . [ABSTRACT FROM AUTHOR]

Given a graph G and a nondecreasing sequence S = (s 1 , ... , s k) of positive integers, the mapping c : V (G) ⟶ { 1 , ... , k } is called an S-packing coloring of G if for any two distinct vertices x and y in c - 1 (i) , the distance between x and y is greater than s i . The smallest integer k such that there exists a (1 , 2 , ... , k) -packing coloring of a graph G is called the packing chromatic number of G, denoted χ ρ (G) . The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all subcubic graphs. In this paper, we prove that the packing chromatic number of any 2-connected bipartite subcubic outerplanar graph is bounded by 7. Furthermore, we prove that every subcubic triangle-free outerplanar graph has a (1, 2, 2, 2)-packing coloring, and that there exists a subcubic outerplanar graph with a triangle that does not admit a (1, 2, 2, 2)-packing coloring. In addition, there exists a subcubic triangle-free outerplanar graph that does not admit a (1, 2, 2, 3)-packing coloring. A similar dichotomy is shown for bipartite outerplanar graphs: every such graph admits an S-packing coloring for S = (1 , 3 , ... , 3) , where 3 appears Δ times (Δ being the maximum degree of vertices), and this property does not hold if one of the integers 3 is replaced by 4 in the sequence S. [ABSTRACT FROM AUTHOR]

Domination game (Brešar et al. in SIAM J Discrete Math 24:979–991, 2010) and total domination game (Henning et al. in Graphs Comb 31:1453–1462 (2015) are by now well established games played on graphs by two players, named Dominator and Staller. In this paper, Z-domination game, L-domination game, and LL-domination game are introduced as natural companions of the standard domination games. Versions of the Continuation Principle are proved for the new games. It is proved that in each of these games the outcome of the game, which is a corresponding graph invariant, differs by at most one depending whether Dominator or Staller starts the game. The hierarchy of the five domination games is established. The invariants are also bounded with respect to the (total) domination number and to the order of a graph. Values of the three new invariants are determined for paths up to a small constant independent from the length of a path. Several open problems and a conjecture are listed. The latter asserts that the L-domination game number is not greater than 6 / 7 of the order of a graph. [ABSTRACT FROM AUTHOR]

Given a graph G, the exact distance-p graph G [ ♮ p ] has V(G) as its vertex set, and two vertices are adjacent whenever the distance between them in G equals p. We present formulas describing the structure of exact distance-p graphs of the Cartesian, the strong, and the lexicographic product. We prove such formulas for the exact distance-2 graphs of direct products of graphs. We also consider infinite grids and some other product structures. We characterize the products of graphs of which exact distance graphs are connected. The exact distance-p graphs of hypercubes Q n are also studied. As these graphs contain generalized Johnson graphs as induced subgraphs, we use some known constructions of their colorings. These constructions are applied for colorings of the exact distance-p graphs of hypercubes with the focus on the chromatic number of Q n [ ♮ p ] for p ∈ { n - 2 , n - 3 , n - 4 } . [ABSTRACT FROM AUTHOR]

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets Vi, i∈{1,…,k}, where each Vi is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpiński-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpiński graphs with base 3, we prove that it is unbounded in the families of Sierpiński graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpiński triangle graphs ST3n is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs SGn with respect to all connected graphs G of order 4. [ABSTRACT FROM AUTHOR]

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets Vi, i∈[k], where each Vi is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that ω(G)=a, χ(G)=b, and χρ(G)=c. If so, we say that (a, b, c) is realizable. It is proved that b=c≥3 implies a=b, and that triples (2,k,k+1) and (2,k,k+2) are not realizable as soon as k≥4. Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on χρ(G) in terms of Δ(G) and α(G) is also proved. [ABSTRACT FROM AUTHOR]

The article offers information on packing chromatic number and 1, 1, 2, 2 colorings. The author stresses that determining whether packing chromatic number is bounded by a constant in the class of all cubic graphs is one of the intriguing problems related to it. Characterization of the Petersen graph is also discussed.

The packing chromatic number $$\chi _{\rho }(G)$$ of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least $$i+1$$ . Let $$S^n$$ be the base-3 Sierpiński graph of dimension n. It is proved that $$\chi _{\rho }(S^1) = 3$$ , $$\chi _{\rho }(S^2) = 5$$ , $$\chi _{\rho }(S^3) = \chi _{\rho }(S^4) = 7$$ , and that $$8\le \chi _\rho (S^n) \le 9$$ holds for any $$n\ge 5$$ . [ABSTRACT FROM AUTHOR]

In this note we characterize the pairs of graphs $$G$$ and $$H$$ , for which $$\gamma (G\,\Box \,H)$$ equals $$\min \{|V(G)|,|V(H)|\}$$ . Notably, assuming that $$|V(G)|\le |V(H)|$$ , $$G$$ can be an arbitrary graph, and $$H$$ is a join $$L\oplus F$$ , where $$L$$ is any spanning supergraph of the graph $$\mathcal{L}(G:A_1,\ldots , A_{\ell })$$ , which is determined by a partition $$(A_1,\ldots , A_{\ell })$$ of $$V(G)$$ and $$F$$ is any graph such that $$|V(F)|\ge |V(G)|-\ell $$ . Furthermore we give some sufficient and some necessary conditions for pairs of graphs $$G$$ and $$H$$ to satisfy $$\gamma (G\,\Box \,H)=\min \{\gamma (G)|V(H)|, |V(G)|\gamma (H)\}.$$ [ABSTRACT FROM AUTHOR]