Communications in Combinatorics and Optimization
Volume:9 Issue: 2, Spring 2024

A $k$-CEC graph is a graph $G$ which has connected domination number $\gamma_{c}(G) = k$ and $\gamma_{c}(G + uv) < k$ for every $uv \in E(\overline{G})$. A $k$-CVC graph $G$ is a $2$-connected graph with  $\gamma_{c}(G) = k$ and $\gamma_{c}(G - v) < k$ for any $v \in V(G)$. A graph is said to be maximal $k$-CVC if it is both $k$-CEC and $k$-CVC. Let $\delta$, $\kappa$, and $\alpha$ be the minimum degree, connectivity, and independence number of $G$, respectively. In this work, we prove that for a maximal $3$-CVC graph, if $\alpha = \kappa$, then $\kappa = \delta$. We additionally consider the class of maximal $3$-CVC graphs with $\alpha < \kappa$ and $\kappa < \delta$, and prove that every $3$-connected maximal $3$-CVC graph when $\kappa < \delta$ is Hamiltonian connected.

A coloring $C=(V_1, \dots, V_k)$ of $G$ partitions the vertex set $V(G)$ into independent sets $V_i$ which are said to be color classes with respect to the coloring $C$. A vertex $v$ is said to have a dominator (dom) color class in $C$ if there is color class $V_i$ such that $v$ is adjacent to all the vertices of $V_i$ and $v$ is said to have an anti-dominator (anti-dom) color class in $C$ if there is color class $V_j$ such that $v$ is not adjacent to any vertex of $V_j$. Dominator coloring of $G$ is a coloring $C$ of $G$ such that every vertex has a dom color class. The minimum number of colors required for a dominator coloring of $G$ is called the dominator chromatic number of $G$, denoted by $\chi_{d}(G)$. Global Dominator coloring of $G$ is a coloring $C$ of $G$ such that every vertex has a dom color class and an anti-dom color class. The minimum number of colors required for a global dominator coloring of $G$ is called the global dominator chromatic number of $G$, denoted by $\chi_{gd}(G)$. In this paper, we give a counterexample for the conjecture posed in [I. Sahul Hamid, M.Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39  (2019), 325--339] that for a graph $G$, if $\chi_{gd}(G)=2\chi_{d}(G)$, then $G$ is a complete multipartite graph. We deduce upper and lower bound for the global dominator chromatic number of Mycielskian of the graph $G$ in terms of dominator chromatic number of $G$.

Let $t_p(G)$ denote the number of paths in a graph $G$ and let $f:E\rightarrow \mathbb{Z}^+$ be an edge labeling of $G$. The weight of a path $P$ is the sum of the labels assigned to the edges of $P$. If the set of weights of the paths in $G$ is $\{1,2,3,\dots,t_p(G)\}$, then $f$ is called a Leech labeling of $G$ and a graph which admits a Leech labeling is called a Leech graph. In this paper, we prove that the complete bipartite graphs $K_{2,n}$ and $K_{3,n}$ are not Leech graphs and determine the maximum possible value that can be given to an edge in the Leech labeling of a cycle.

Given a graph $G=(V,E)$,  a  function  $f:V\to \{0,1,2,3,4\}$ is a triple Roman  dominating function (TRDF)  of $G$, for each vertex $v\in V$,  (i) if $f (v ) = 0 $, then  $v$ must have either one neighbour in $V_4$, or either two neighbours in $V_2 \cup  V_3$ (one neighbour in $V_3$) or either three neighbours in $V_2 $, (ii) if $f (v ) = 1 $, then $v$ must have either one neighbour in  $V_3 \cup  V_4$  or either two neighbours in $V_2 $, and if $f (v ) = 2 $, then $v$ must have one neighbour in $V_2 \cup  V_3\cup  V_4$. The triple Roman  domination number of $G$ is the  minimum weight of an TRDF  $f$  of $G$, where the weight of $f$ is $\sum_{v\in V}f(v)$.  The triple  Roman  domination problem is to compute the  triple Roman  domination number of a given graph.  In this paper, we study the triple  Roman  domination problem. We show that   the problem is NP-complete for  the  star convex bipartite  and the   comb convex bipartite graphs and is APX-complete for graphs of degree at~most~4. We propose a linear-time algorithm for computing  the triple Roman  domination number of proper interval graphs.  We also   give an $( 2 H(\Delta(G)+1) -1  )$-approximation algorithm  for solving the problem  for any graph $G$,  where   $  \Delta(G)$ is the maximum degree of $G$ and $H(d)$ denotes the first $d$ terms of the harmonic  series. In addition, we prove  that  for any $\varepsilon>0$  there is no  $(1/4-\varepsilon)\ln|V|$-approximation  polynomial-time   algorithm for solving  the problem on bipartite and split  graphs, unless NP $\subseteq$ DTIME $(|V|^{O(\log\log|V |)})$.

A total coloring of a graph $G$ is an assignment of colors to all the elements (vertices and edges) of the graph in such a way that no two adjacent or incident elements receive the same color. The total chromatic number of $G$, denoted by $\chi''(G)$, is the minimum number of colors which need for total coloring of $G$. The Total Coloring Conjecture (TCC) made independently by Behzad and Vizing which claims that, $\Delta(G)+1 \leq \chi''(G) \leq \Delta(G)+2 $, where $\Delta(G)$ is the maximum degree of $G$. The lower bound is sharp and the upper bound remains to be proved. In this paper, we prove the TCC for certain classes of lexicographic and deleted lexicographic products of graphs. Also, we obtained the lower bound for certain classes of these products.

The main aim of the paper is to give the crossing number of the join product $G^\ast + D_n$ for the graph $G^\ast$ isomorphic to 4-regular graph on six vertices except for two distinct edges with no common vertex such that two remaining vertices are still adjacent, and where $D_n$ consists of $n$ isolated vertices. The proofs are done with possibility of an existence of a separating cycle in some particular drawing of the investigated graph $G^\ast$ and also with the help of well-known exact values for crossing numbers of join products of two subgraphs $H_k$ of $G^\ast$ with discrete graphs.

We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the $g$-Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs.

A square is a concatenation of two identical words, and a word $w$ is said to have a square $yy$ if $w$ can be written as $xyyz$ for some words $x$ and $z$. It is known that the ratio of the number of distinct squares in a word to its length is less than two, and any location of a word could begin with two distinct squares which are appearing in the word for the last time. A square whose first location starts with the last occurrence of two distinct squares is an FS-double square. We explore and identify the conditions under which a sequence of locations in a word starts with FS-double squares. We first find the structure of a word that begins with two consecutive FS-double squares and obtain its properties that enable us to extend the sequence of FS-double squares. It is proved that the length of the longest sequence of consecutive FS-double squares in a word of length $n$ is at most $\frac{n}{7}$. We show that the squares in the longest sequence of consecutive FS-double squares are conjugates.

The harmonic polynomial was defined in order to understand better the harmonic topological index. Here, we obtain several properties of this polynomial, and we prove that several properties of a graph can be deduced from its harmonic polynomial. Also, we prove that graphs with the same harmonic polynomial share many properties although they are not necessarily isomorphic.

Let $G=(V,E)$ be a connected graph with the vertex-set $V$ and  the edge-set $E$.    The subdivision graph $S(G)$ of the graph $G$ is obtained from $G$ by adding a vertex in the middle of every edge of $G$.  In this paper, we investigate some properties of the graphs  $S(G)$ and $L(S(G))$, where $L(S(G))$ is the line graph of $S(G)$. We will see that $S(G)$ and  $L(S(G))$  inherit some  properties of $G$.    For instance, we show that if $G \ncong C_n$, then $Aut(G) \cong Aut(L(S(G)))$ (as abstract groups), where $C_n$ is the cycle of order $n$.

A triangular tile latching system consists of a set $\Sigma$ of equilateral triangular tiles with at least one latchable side and an attachment rule which permits two tiles to get latched along a latchable side. In this paper we determine the language generated by a triangular tile latching system in terms of planar graphs.

Domination in graphs and coloring of graphs are two main areas of investigation in graph theory. Power domination is a variant of domination in graphs introduced in the study of the problem of monitoring an electric power system. Based on the notions of power domination and coloring of a graph, the concept of power dominator coloring of a graph was introduced. The minimum number of colors required for power dominator coloring of a graph $G$ is called the power dominator chromatic number $\chi_{pd}(G)$ of $G,$ which has been computed for some classes of graphs. Here we compute the power dominator chromatic number for splitting graphs of certain classes of graphs.

A $\mu$-way $(v,k,t)$ trade $T$ of volume $m$ consists of $\mu$ pairwise disjoint collections $T_1, \ldots ,T_{\mu}$, each of $m$ blocks of size $k$ such that for every $t$-subset of a $v$-set $V,$ the number of blocks containing this $t$-subset is the same in each $T_i$ for $1\leq i\leq \mu$. If any $t$-subset of the $v$-set $V$ occurs at most once in each $T_i$ for $1\leq i\leq \mu$, then $T$ is called a $\mu$-way $(v,k,t)$ Steiner trade. In 2016, it was proved that there exists a 3-way $(v,k,2)$ Steiner trade of volume $m$ when $12(k-1)\leq m$ for each $k$. Here we improve the lower bound to $8(k-1)$ for even $k$, by  using a recursive construction.

Let $k\ge 1$ be an integer, and let $D$ be a finite and simple digraph with vertex set $V(D)$. A signed total Italian $k$-dominating function (STIkDF) on a digraph $D$ is a function $f:V(D)\rightarrow\{-1,1,2\}$ satisfying the conditions that (i) $\sum_{x\in N^-(v)}f(x)\ge k$ for each vertex $v\in V(D)$, where $N^-(v)$ consists of all vertices of $D$ from which arcs go into $v$, and (ii) each vertex $u$ with $f(u)=-1$ has an in-neighbor $v$ for which $f(v)=2$ or two in-neighbors $w$ and $z$ with $f(w)=f(z)=1$. The weight of an STIkDF $f$ is $\omega(f)=\sum_{v\in V(D)}f(v)$. The signed total Italian $k$-domination number $\gamma_{stI}^k(D)$ of $D$ is the minimum weight of an STIkDF on $D$. In this paper we initiate the study of the signed total Italian $k$-domination number of digraphs, and we  present different bounds on $\gamma_{stI}^k(D)$. In addition, we determine the signed total Italian $k$-domination number of some classes of digraphs.

We propose logarithmic-barrier decomposition-based interior-point algorithms for solving two-stage stochastic quadratically constrained convex quadratic programming problems in a Hilbert space. We prove the polynomial complexity of the proposed algorithms, and show that this complexity is independent on the choice of the Hilbert space, and hence it coincides with the best-known complexity estimates in the finite-dimensional case. We also apply our results on a concrete example from the stochastic control theory.