On the independence number of the power graph of a finite group

The power graph ${\Gamma }_G$ of a finite group $G$ is the graph whose vertex set is $G$, two distinct elements being adjacent if one is a power of the other. In this paper, we give sharp lower and upper bounds for the independence number of ${\Gamma }_G$ and characterize the groups achieving the bounds. Moreover, we determine the independence number of ${\Gamma }_G$ if $G$ is cyclic, dihedral or generalized quaternion. Finally, we classify all finite groups $G$ whose power graphs have independence number 3 or $n?2$, where $n$ is the order of $G$.     

Symmetric cubic graphs with solvable automorphism groups

A cubic graph $\Gamma$ is $G$-arc-transitive if $G\le \mathrm{Aut}\left(\Gamma \right)$ acts transitively on the set of arcs of $\Gamma$, and $G$-basic if $\Gamma$ is $G$-arc-transitive and $G$ has no non-trivial normal subgroup with more than two orbits. Let $G$ be a solvable group. In this paper, we first classify all connected $G$-basic cubic graphs and determine the group structure for every $G$. Then, combining covering techniques, we prove that a connected cubic $G$-arc-transitive graph is either a Cayley graph, or its full automorphism group is of type $2^2$, that is, a $2$-regular group with no involution reversing an edge, and has a non-abelian normal subgroup such that the corresponding quotient graph is the complete bipartite graph of order $6$.     

Properties of minimally t-tough graphs

A graph $G$ is minimally $t$-tough if the toughness of $G$ is $t$ and the deletion of any edge from $G$ decreases the toughness. Kriesell conjectured that for every minimally $1$-tough graph the minimum degree $\delta \left(G\right)=2$. We show that in every minimally $1$-tough graph $\delta \left(G\right)\le \frac{n}{3}+1$. We also prove that every minimally $1$-tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number $t$ any graph can be embedded as an induced subgraph into a minimally $t$-tough graph.     

A characterization of cycle-forced bipartite graphs

A forced cycle$C$ of a graph $G$ is a cycle in $G$ such that $G?V\left(C\right)$ has a unique perfect matching. A graph $G$ is a cycle-forced graph if every cycle in $G$ is a forced cycle. In this paper, we give a characterization of cycle-forced hamiltonian bipartite graphs.     

Star saturation number of random graphs

For a given graph $F$, the $F$-saturation number of a graph $G$ is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. Recently, the $F$-saturation number of the Erd?s–Rényi random graph $\mathbb{G}(n,p)$ has been determined asymptotically for any complete graph $F$. In this paper, we give an asymptotic formula for the $F$-saturation number of $\mathbb{G}(n,p)$ when $F$ is a star graph.     

Spectral radius of power graphs on certain finite groups

The power graph of a group $G$ is a graph with vertex set $G$ and two distinct vertices are adjacent if and only if one is an integral power of the other. In this paper we find both upper and lower bounds for the spectral radius of power graph of cyclic group $C_n$ and characterize the graphs for which these bounds are extremal. Further we compute spectra of power graphs of dihedral group $D_{2n}$ and dicyclic group $Q_{4n}$ partially and give bounds for the spectral radii of these graphs.     

Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths

It is well-known that the paths are determined by the spectrum of the adjacency matrix. For digraphs, every digraph whose underlying graph is a tree is cospectral to its underlying graph with respect to the Hermitian adjacency matrix ($H$-cospectral). Thus every (simple) digraph whose underlying graph is isomorphic to $P_n$ is $H$-cospectral to $P_n$. Interestingly, there are others. This paper finds digraphs that are $H$-cospectral with the path graph $P_n$ and whose underlying graphs are nonisomorphic, when $n$ is odd, and finds that such graphs do not exist when $n$ is even. In order to prove this result, all digraphs whose Hermitian spectral radius is smaller than 2 are determined.     

On the metric dimension of incidence graphs

A resolving set for a graph $\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The metric dimension$\mu \left(\Gamma \right)$ is the smallest size of a resolving set for $\Gamma$. We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that $\mu \left(\Gamma \right)=O(\sqrt{n}logn)$ (where $n$ is the number of vertices).     

Doppelgangers and Lemke graphs

Let $G$ be a connected graph. A configuration of pebbles on $G$ is a function that assigns a nonnegative integer to each vertex. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if after making pebbling moves any vertex can get at least one pebble. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)?q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of pebbling moves so that at least two pebbles can be placed on any vertex. A graph without the two-pebbling property is called a Lemke graph. Previously, an infinite family of Lemke graphs was shown to exist by subdividing edges of the original Lemke graph. In this paper, we introduce a new way to create infinite families of Lemke graphs based on adding vertices as well as subdividing edges. We also characterize the configurations that violate the two-pebbling property on these graphs and conjecture another infinite family of Lemke graphs that generalizes the original Lemke graph.     

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.     

Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This paper deals with the Cayley graph $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$, where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that $\text{Aut}\left(\mathrm{Cay}({\mathrm{Sym}}_n,T_n)\right)$ is the product of the left translation group and a dihedral group ${\mathsf{D}}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $\Gamma$ of $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$ induced by the set $T_n$. In particular, $\Gamma$ is a $2(n?2)$-regular graph whose automorphism group is ${\mathsf{D}}_{n+1},$ $\Gamma$ has as many as $n+1$ maximal cliques of size $2$, and its subgraph $\Gamma \left(V\right)$ whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of ${\mathsf{D}}_{n+1}$ of order $n+1$ with regular Cayley maps on ${\text{Sym}}_n$ is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on ${\text{Sym}}_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.     

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

List star chromatic index of sparse graphs

A star edge-coloring of a graph $G$ is a proper edge coloring such that every 2-colored connected subgraph of $G$ is a path of length at most 3. For a graph $G$, let the list star chromatic index of $G$, $c{h}_s^{\prime }\left(G\right)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from $L$. Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph $G$ is less than $\frac{14}{5}$ (resp. 3), then $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$ (resp. $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+3$).     

An improved upper bound on the maximum degree of terminal-pairable complete graphs

A graph $G$ is terminal-pairable with respect to a demand (loopless) multigraph $D$ on the same vertex set as $G$, if there exist edge-disjoint paths joining the end vertices of every demand edge of $D$. In this short note, we improve the upper bound on the largest $\Delta \left(n\right)$ with the property that the complete graph on $n$ vertices is terminal-pairable with respect to any demand multigraph of maximum degree at most $\Delta \left(n\right)$. This disproves a conjecture originally stated by Csaba, Faudree, Gyárfás, Lehel and Schelp.     

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.