Search

A dominating (respectively, total dominating) set S of a digraph D is a set of vertices in D such that the union of the closed (respectively, open) out‐neighborhoods of vertices in S equals the vertex set of D. The minimum size of a dominating (respectively, total dominating) set of D is the domination (respectively, total domination) number of D, denoted γ(D) (respectively, γt(D)). The maximum number of pairwise disjoint closed (respectively, open) in‐neighborhoods of D is denoted by ρ(D) (respectively, ρo(D)). We prove that in digraphs whose underlying graphs have girth at least 7, the closed (respectively, open) in‐neighborhoods enjoy the Helly property, and use these two results to prove that in any ditree T (i.e., a digraph whose underlying graph is a tree), γt(T)=ρo(T) and γ(T)=ρ(T). By using the former equality we then prove that γt(G×T)=γt(G)γt(T), where G is any digraph and T is any ditree, each without a source vertex, and G×T is their direct product. From the equality γ(T)=ρ(T) we derive the bound γ(G□T)≥γ(G)γ(T), where G is an arbitrary digraph, T an arbitrary ditree and G□T is their Cartesian product. In general digraphs this Vizing‐type bound fails, yet we prove that for any digraphs G and H, where γ(G)≥γ(H), we have γ(G□H)≥12γ(G)(γ(H)+1). This inequality is sharp as demonstrated by an infinite family of examples. Ditrees T and digraphs H enjoying γ(T□H)=γ(T)γ(H) are also investigated. [ABSTRACT FROM AUTHOR]

A geodesic packing of a graph G is a set of vertex-disjoint maximal geodesics. The maximum cardinality of a geodesic packing is the geodesic packing number gpack (G). It is proved that the decision version of the geodesic packing number is NP-complete. We also consider the geodesic transversal number, gt (G) , which is the minimum cardinality of a set of vertices that hit all maximal geodesics in G. While gt (G) ≥ gpack (G) in every graph G , the quotient gt (G) / gpack (G) is investigated. By using the rook's graph, it is proved that there does not exist a constant C < 3 such that gt (G) gpack (G) ≤ C would hold for all graphs G. If T is a tree, then it is proved that gpack (T) = gt (T) , and a linear algorithm for determining gpack (T) is derived. The geodesic packing number is also determined for the strong product of paths. [ABSTRACT FROM AUTHOR]

For a non-decreasing sequence S = (s 1 , s 2 , ...) of positive integers, a partition of the vertex set of a graph G into subsets X 1 , ... , X ℓ , such that vertices in X i are pairwise at distance greater than s i for every i ∈ { 1 , ... , ℓ } , is called an S -packing ℓ -coloring of G. The minimum ℓ for which G admits an S -packing ℓ -coloring is called the S -packing chromatic number of G. In this paper, we consider S -packing colorings of the integer distance graphs with respect two positive integers k and t , which are the graphs whose vertex set is Z , and two vertices x , y ∈ Z are adjacent whenever | x − y | ∈ { k , t }. We complement partial results from two earlier papers, thus determining all values of the S -packing chromatic numbers of these distance graphs for all sequence S such that s i ≤ 2 for all i. In particular, if S = (1 , 1 , 2 , 2 , ...) , then the S -packing chromatic number is 2 if k + t is even, and 4 otherwise, while if S = (1 , 2 , 2 , ...) , then the S -packing chromatic number is 5, unless { k , t } = { 2 , 3 } when it is 6; when S = (2 , 2 , 2 , ...) , the corresponding formula is more complex. • Studies S-packing colorings for graphs using non-decreasing sequences of integers. • Analyses integer distance graphs based on two positive integers. • Determines S-packing chromatic numbers for cases where sequence values are at most 2. • Complements prior research on S-packing chromatic numbers for specific sequences. [ABSTRACT FROM AUTHOR]

• An extension of the concept of uniquely colorable graphs. • Uniquely colorable graphs up to automorphisms. • Efficient recognition of uniquely colorable graphs up to automorphisms. We extend the concept of uniquely colorable graphs and say that a graph G is χ -iso-unique if for every two proper colorings c : V (G) → { 1 , ... , χ (G) } and d : V (G) → { 1 , ... , χ (G) } there exists an automorphism φ of G such that for any i ∈ { 1 , ... , χ (G) } there exists j ∈ { 1 , ... , χ (G) } so that φ maps c − 1 (i) onto d − 1 (j). First, we prove some general properties about degrees of vertices of χ -iso-unique graphs G , and then focus on non-bipartite outerplanar χ -iso-unique graphs. As proved by Chartrand and Geller back in 1969, uniquely 3-colorable outerplanar graphs are precisely the 2-connected outerplanar graphs in which all induced cycles are triangles. We prove that a χ -iso-unique outerplanar graph G with χ (G) = 3 contains at most one inner face, which is not a triangle, and it is isomorphic to C 5 if it exists. Besides maximal outerplanar graphs, there is just one additional family of 2-connected outerplanar graphs that are χ -iso-unique, and they contain one facial 5-cycle. In contrast to the situation in uniquely colorable graphs, we find two families of outerplanar χ -iso-unique graphs having cut-vertices, and finally, we characterize all outerplanar χ -iso-unique graphs. We also show that χ -iso-unique outerplanar graphs can be recognized efficiently. [ABSTRACT FROM AUTHOR]

The Grundy domination number, γ gr (G) , of a graph G is the maximum length of a sequence (v 1 , v 2 , ... , v k) of vertices in G such that for every i ∈ { 2 , ... , k } , the closed neighborhood N [ v i ] contains a vertex that does not belong to any closed neighborhood N [ v j ] , where j < i. It is well known that the Grundy domination number of any graph G is greater than or equal to the upper domination number Γ (G) , which is in turn greater than or equal to the independence number α (G). In this paper, we initiate the study of the class of graphs G with Γ (G) = γ gr (G) and its subclass consisting of graphs G with α (G) = γ gr (G). We characterize the latter class of graphs among all twin-free connected graphs, provide a number of properties of these graphs, and prove that the hypercubes are members of this class. In addition, we give several necessary conditions for graphs G with Γ (G) = γ gr (G) and present large families of such graphs. [ABSTRACT FROM AUTHOR]

An open packing in a graph G is a set S of vertices in G such that no two vertices in S have a common neighbor in G. The injective chromatic number χ i (G) of G is the smallest number of colors assigned to vertices of G such that each color class is an open packing. Alternatively, the injective chromatic number of G is the chromatic number of the two-step graph of G , which is the graph with the same vertex set as G in which two vertices are adjacent if they have a common neighbor. The concept of injective coloring has been studied by many authors, while in the present paper we approach it from two novel perspectives, related to open packings and the two-step graph operation. We prove several general bounds on the injective chromatic number expressed in terms of the open packing number. In particular, we prove that χ i (G) ≥ 1 2 + 1 4 + 2 m − n ρ o holds for any connected graph G of order n ≥ 2 , size m , and the open packing number ρ o , and characterize the class of graphs attaining the bound. Regarding the well known bound χ i (G) ≥ Δ (G) , we describe the family of extremal graphs and prove that deciding when the equality holds (even for regular graphs) is NP-complete, solving an open problem from an earlier paper. Next, we consider the chromatic number of the two-step graph of a graph, and compare it with the clique number and the maximum degree of the graph. We present two large families of graphs in which χ i (G) equals the cardinality of a largest clique of the two-step graph of G. Finally, we consider classes of graphs that admit an injective coloring in which all color classes are maximal open packings. We give characterizations of three subclasses of these graphs among graphs with diameter 2, and find a partial characterization of hypercubes with this property. [ABSTRACT FROM AUTHOR]