Power domination in certain chemical structures

Let $G(V,E)$ be a simple connected graph. A set $S\subseteq V$ is a power dominating set (PDS) of G, if every vertex and every edge in the system is observed following the observation rules of power system monitoring. The minimum cardinality of a PDS of a graph G is the power domination number ${\gamma }_p(G)$. In this paper, we establish a fundamental result that would provide a lower bound for the power domination number of a graph. Further, we solve the power domination problem in polyphenylene dendrimers, Rhenium Trioxide (ReO₃) lattices and silicate networks.     

Restrained bondage in graphs

Let $G=(V,E)$ be a graph. A set $S?V$ is a restrained dominating set if every vertex not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V?S$. The restrained domination number of $G$, denoted by ${\gamma }_r\left(G\right)$, is the smallest cardinality of a restrained dominating set of $G$. We define the restrained bondage number $b_r\left(G\right)$ of a nonempty graph $G$ to be the minimum cardinality among all sets of edges $E^{\prime }?E$ for which ${\gamma }_r(G?E^{\prime })>{\gamma }_r\left(G\right)$. Sharp bounds are obtained for $b_r\left(G\right)$, and exact values are determined for several classes of graphs. Also, we show that the decision problem for $b_r\left(G\right)$ is NP-complete even for bipartite graphs.     

Total domination in inflated graphs

The inflation $G_I$ of a graph $G$ is obtained from $G$ by replacing every vertex $x$ of degree $d\left(x\right)$ by a clique $X=K_{d\left(x\right)}$ and each edge $xy$ by an edge between two vertices of the corresponding cliques $X$ and $Y$ of $G_I$ in such a way that the edges of $G_I$ which come from the edges of $G$ form a matching of $G_I$. A set $S$ of vertices in a graph $G$ is a total dominating set, abbreviated TDS, of $G$ if every vertex of $G$ is adjacent to a vertex in $S$. The minimum cardinality of a TDS of $G$ is the total domination number ${\gamma }_t\left(G\right)$ of $G$. In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if $G$ is a connected graph of order $n\ge 2$, then ${\gamma }_t\left(G_I\right)\ge 2n/3$, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of $G$ to be at least $2$, then we show that ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if $G$ has a perfect matching. If we increase the minimum degree requirement of $G$ to be at least $3$, then we show ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if every minimum TDS of $G_I$ is a perfect total dominating set of $G_I$, where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set.     

On k-domination and j-independence in graphs

Let $G$ be a graph and let $k$ and $j$ be positive integers. A subset $D$ of the vertex set of $G$ is a $k$-dominating set if every vertex not in $D$ has at least $k$ neighbors in $D$. The $k$-domination number ${\gamma }_k\left(G\right)$ is the cardinality of a smallest $k$-dominating set of $G$. A subset $I?V\left(G\right)$ is a $j$-independent set of $G$ if every vertex in $I$ has at most $j?1$ neighbors in $I$. The $j$-independence number ${\alpha }_j\left(G\right)$ is the cardinality of a largest $j$-independent set of $G$. In this work, we study the interaction between ${\gamma }_k\left(G\right)$ and ${\alpha }_j\left(G\right)$ in a graph $G$. Hereby, we generalize some known inequalities concerning these parameters and put into relation different known and new bounds on $k$-domination and $j$-independence. Finally, we will discuss several consequences that follow from the given relations, while always highlighting the symmetry that exists between these two graph invariants.     

A note on the list vertex arboricity of toroidal graphs

The vertex arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of colors required to color the vertices of $G$ such that no cycle is monochromatic. The list vertex arboricity $a_l\left(G\right)$ is the list-coloring version of this concept. In this note, we prove that if $G$ is a toroidal graph, then $a_l\left(G\right)\le 4$; and $a_l\left(G\right)=4$ if and only if $G$ contains $K_7$ as an induced subgraph.     

Sum choice number of generalized θ-graphs

Let $G=\left(VE\right)$ be a simple graph and for every vertex $v\in V$ let $L\left(v\right)$ be a set (list) of available colors. $G$ is called $L$-colorable if there is a proper coloring $\phi$ of the vertices with $\phi \left(v\right)\in L\left(v\right)$ for all $v\in V$. A function $f:V\to \mathbb{N}$ is called a choice function of $G$ and $G$ is said to be $f$-list colorable if $G$ is $L$-colorable for every list assignment $L$ choice function is defined by $size\left(f\right)={\sum }_{v\in V}f\left(v\right)$ and the sum choice number ${\chi }_{sc}\left(G\right)$ denotes the minimum size of a choice function of $G$.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For $r\ge 3$ a generalized ${\theta }_{k_1{k}_2\dots k_r}$-graph is a simple graph consisting of two vertices $v_1$ and $v_2$ connected by $r$ internally vertex disjoint paths of lengths $k_1,k_2,\dots ,k_r$ $(k_1\le k_2\le ?\le k_r)$.In 2014, Carraher et al. determined the sum-paintability of all generalized $\theta$-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized $\theta$-graphs with $k_1\ge 2$ and characterize all generalized $\theta$-graphs $G$ which attain the trivial upper bound $\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$.     

On graphs with largest possible game domination number

Let $\gamma \left(G\right)$ and ${\gamma }_g\left(G\right)$ be the domination number and the game domination number of a graph $G$, respectively. In this paper ${\gamma }_g$-maximal graphs are introduced as the graphs $G$ for which ${\gamma }_g\left(G\right)=2\gamma \left(G\right)?1$ holds. Large families of ${\gamma }_g$-maximal graphs are constructed among the graphs in which their sets of support vertices are minimum dominating sets. ${\gamma }_g$-maximal graphs are also characterized among the starlike trees, that is, trees which have exactly one vertex of degree at least $3$.     

Moplex orderings generated by the LexDFS algorithm

Let $G$ be a graph with vertex set $V$. A moplex of $G$ is both a clique and a module whose neighborhood is a minimal separator in $G$ or empty. A moplex ordering of $G$ is an ordered partition $(X_1,X_2,?,X_k)$ of $V$ for some integer $k$ into moplexes which are defined in the successive transitory elimination graphs, i.e., for $1?i?k?1$, $X_i$ is a moplex of the graph $G_i$ induced by ${\cup }_{j=i}^k{X}_j$ and $X_k$ induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on $G$ belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on $G$ defines a moplex ordering of $G$, which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques.     

Fixed-parameter algorithms for vertex cover P3

Let $P_{\ell }$ denote a path in a graph $G=(V,E)$ with $\ell$ vertices. A vertex cover $P_{\ell }$ set $C$ in $G$ is a vertex subset such that every $P_{\ell }$ in $G$ has at least a vertex in $C$. The Vertex Cover$P_{\ell }$ problem is to find a vertex cover $P_{\ell }$ set of minimum cardinality in a given graph. This problem is NP-hard for any integer $\ell ⩾2$. The parameterized version of Vertex Cover$P_{\ell }$ problem called $k$-Vertex Cover$P_{\ell }$ asks whether there exists a vertex cover $P_{\ell }$ set of size at most $k$ in the input graph. In this paper, we give two fixed parameter algorithms to solve the $k$-Vertex Cover$P_3$ problem. The first algorithm runs in time $O^1\left(1.7964^k\right)$ in polynomial space and the second algorithm runs in time $O^1\left(1.7485^k\right)$ in exponential space. Both algorithms are faster than previous known fixed-parameter algorithms.     

Global defensive alliances of trees and Cartesian product of paths and cycles

Given a graph $G$, a defensive alliance of $G$ is a set of vertices $S?V\left(G\right)$ satisfying the condition that for each $v\in S$, at least half of the vertices in the closed neighborhood of $v$ are in $S$. A defensive alliance $S$ is called global if every vertex in $V\left(G\right)?S$ is adjacent to at least one member of the defensive alliance $S$. The global defensive alliance number of $G$, denoted ${\gamma }_a\left(G\right)$, is the minimum size around all the global defensive alliances of $G$. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete $k$-ary trees for $k=2,3,4$. We also establish upper bounds and lower bounds for ${\gamma }_a(P_m\times P_n),{\gamma }_a(C_m\times P_n)$ and ${\gamma }_a(C_m\times C_n)$, and show that the bounds are sharp for certain $m,n$.     

A way to construct independence equivalent graphs

Let us denote the independence polynomial of a graph by $I_G\left(x\right)$. If $I_G\left(x\right)=I_H\left(x\right)$ implies that $G?H$ then we say $G$ is independence unique. For graph $G$ and $H$ if $I_G\left(x\right)=I_H\left(x\right)$ but $G$ and $H$ are not isomorphic, then we say $G$ and $H$ are independence equivalent. In [7], Brown and Hoshino gave a way to construct independent equivalent graphs for circulant graphs. In this work we give a way to construct the independence equivalent graphs for general simple graphs and obtain some properties of the independence polynomial of paths and cycles.     

On (Kq,k) vertex stable graphs with minimum size

A graph $G$ is a $(K_q,k)$ vertex stable graph if it contains a $K_q$ after deleting any subset of $k$ vertices. We give a characterization of $(K_q,k)$ vertex stable graphs with minimum size for $q=3,4,5$.     

Indicated coloring of graphs

We study a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben’s strategy) is called the indicated chromatic number of $G$, and denoted by ${\chi }_i\left(G\right)$. We approach the question how much ${\chi }_i\left(G\right)$ differs from the usual chromatic number $\chi \left(G\right)$. In particular, whether there is a function $f$ such that ${\chi }_i\left(G\right)?f\left(\chi \left(G\right)\right)$ for every graph $G$. We prove that $f$ cannot be linear with leading coefficient less than $4/3$. On the other hand, we show that the indicated chromatic number of random graphs is bounded roughly by $4\chi \left(G\right)$. We also exhibit several classes of graphs for which ${\chi }_i\left(G\right)=\chi \left(G\right)$ and show that this equality for any class of perfect graphs implies Clique-Pair Conjecture for this class of graphs.