Zoltán L. Blázsik

A set S of vertices in an isolate-free graph G is a total dominating set if every vertex of G is adjacent to some other vertex in S . A total coalition in G consists of two disjoint sets of vertices X and Y of G , neither of which is a total dominating set but whose union $$X \cup Y$$ X ∪ Y is a total dominating set of G . Such sets X and Y are said to form a total coalition. A total coalition partition in G is a vertex partition $$\Psi = \{V_1,V_2,\ldots ,V_k\}$$ Ψ = { V 1 , V 2 , … , V k } such that for all $$i \in [k]$$ i ∈ [ k ] , the set $$V_i$$ V i forms a total coalition with another set $$V_j$$ V j for some j , where $$j \in [k] \setminus \{i\}$$ j ∈ [ k ] \ { i } . We emphasize that none of the sets in $$\Psi $$ Ψ is a total dominating set of G . The total coalition number $$C_t(G)$$ C t ( G ) in G equals the maximum order of a total coalition partition in G . We study total coalitions in claw-free cubic graphs with certain structural properties, namely, graphs containing double-bonded triangle-units, that is, two vertex disjoint triangles joined by two edges.

We investigate the extremal properties of saturated partial plane embeddings of maximal planar graphs. For a planar graph $G$, the plane-saturation number $\mathrm{sat}_{\mathcal{P}}(G)$ denotes the minimum number of edges in a plane subgraph of $G$ such that the addition of any edge either violates planarity or results in a graph that is not a subgraph of $G$. We focus on maximal planar graphs and establish an upper bound on $\mathrm{sat}_{\mathcal{P}}(G)$ by showing there exists a universal constant $ε> 0$ such that $\mathrm{sat}_{\mathcal{P}}(G) < (3-ε)v(G)$ for any maximal planar graph $G$ with $v(G) \geq 16$. This answers a question posed by Clifton and Simon. Additionally, we derive lower bound results and demonstrate that for maximal planar graphs with sufficiently large number of vertices, the minimum ratio $\mathrm{sat}_{\mathcal{P}}(G)/e(G)$ lies within the interval $(1/16, 1/9 + o(1)]$.

In a directed graph $D$, a vertex subset $S\subseteq V$ is a total dominating set if every vertex of $D$ has an in-neighbor from $S$. A total dominating set exists if and only if every vertex has at least one in-neighbor. We call the orientation of such directed graphs valid. The total domination number of $D$, denoted by $γ_t(D)$, is the size of the smallest total dominating set of $D$. For an undirected graph $G$, we investigate the upper (or lower) orientable total domination number of $G$, denoted by $\mathrm{DOM}_t(G)$ (or $\mathrm{dom}_t(G)$), that is the maximum (or minimum) of the total domination numbers over all valid orientations of $G$. We characterize those graphs for which $\mathrm{DOM}_t(G)=|V(G)|-1$, and consequently we show that there exists a family of graphs for which $\mathrm{DOM}_t(G)$ and $\mathrm{dom}_t(G)$ can be as far as possible, namely $\mathrm{DOM}_t(G)=|V(G)|-1$ and $\mathrm{dom}_t(G)=3$.