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$.     

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.     

Kirchhoff index in line,subdivision and total graphs of a regular graph

Let $G$ be a connected regular graph and $l\left(G\right)$, $s\left(G\right)$, $t\left(G\right)$ the line, subdivision, total graphs of $G$, respectively. In this paper, we derive formulae and lower bounds of the Kirchhoff index of $l\left(G\right)$, $s\left(G\right)$ and $t\left(G\right)$, respectively. In particular, we give special formulae for the Kirchhoff index of $l\left(G\right)$, $s\left(G\right)$ and $t\left(G\right)$, where $G$ is a complete graph $K_n$, a regular complete bipartite graph $K_{n,n}$ and a cycle $C_n$.     

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.     

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.     

Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph $G$, denoted ${\chi }_D\left(G\right)$, is defined as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism of $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma$ defined over certain abelian groups $A$ with $\left|A\right|=n$, and show that with probability at least $1?n^{?\Omega (logn)}$, ${\chi }_D\left(\Gamma \right)\le \chi \left(\Gamma \right)+1$.     

On the facial Thue choice index of plane graphs

Let $G$ be a plane graph, and let $\phi$ be a colouring of its edges. The edge colouring $\phi$ of $G$ is called facial non-repetitive if for no sequence $r_1,r_2,\dots ,r_{2n}$, $n\ge 1$, of consecutive edge colours of any facial path we have $r_i=r_{n+i}$ for all $i=1,2,\dots ,n$. Assume that each edge $e$ of a plane graph $G$ is endowed with a list $L\left(e\right)$ of colours, one of which has to be chosen to colour $e$. The smallest integer $k$ such that for every list assignment with minimum list length at least $k$ there exists a facial non-repetitive edge colouring of $G$ with colours from the associated lists is the facial Thue choice index of $G$, and it is denoted by ${\pi }_{fl}\left(G\right)$. In this article we show that ${\pi }_{fl}^{\prime }\left(G\right)\le 291$ for arbitrary plane graphs $G$. Moreover, we give some better bounds for special classes of plane graphs.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

Large values of the clustering coefficient

A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (1998), is the clustering coefficient of a graph $G$. It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex $u$ of $G$ is the relative density $m\left(G\left[N_G\left(u\right)\right]\right)∕\left(\genfrac{}{}{0ex}{}{d_G\left(u\right)}{2}\right)$ of its neighborhood if $d_G\left(u\right)$ is at least $2$, and $0$ otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size.We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge.