Pentavalent symmetric graphs admitting transitive non-abelian characteristically simple groups

Let $\Gamma$ be a graph and let $G$ be a group of automorphisms of $\Gamma$. The graph $\Gamma$ is called $G$-normal if $G$ is normal in the automorphism group of $\Gamma$. Let $T$ be a finite non-abelian simple group and let $G=T^l$ with $l\ge 1$. In this paper we prove that if every connected pentavalent symmetric $T$-vertex-transitive graph is $T$-normal, then every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal. This result, among others, implies that every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal except $T$ is one of 57 simple groups. Furthermore, every connected pentavalent symmetric $G$-regular graph is $G$-normal except $T$ is one of 20 simple groups, and every connected pentavalent $G$-symmetric graph is $G$-normal except $T$ is one of 17 simple groups.     

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

Dyadic representations of graphs

A graph $G$ is dyadic provided it has a representation $v\to S_v$ from vertices $v$ of $G$ to subtrees $S_v$ of a host tree $T$ with maximum degree 3 such that $\left(i\right)$$v$ and $w$ are adjacent in $G$ if and only if $S_v$ and $S_w$ share at least three nodes and $\left(ii\right)$ each edge of $T$ is used by exactly two representing subtrees. We show that a connected graph is dyadic if and only if it can be constructed from edges and cycles by gluing vertices to vertices and edges to edges.     

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.     

Forcing faces in plane bipartite graphs (II)

The concept of forcing faces of a plane bipartite graph was first introduced in Che and Chen (2008) [3] [Z. Che, Z. Chen, Forcing faces in plane bipartite graphs, Discrete Mathematics 308 (2008) 2427–2439], which is a natural generalization of the concept of forcing hexagons of a hexagonal system introduced in Che and Chen (2006) [2] [Z. Che and Z. Chen, Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (2006) 649–668]. In this paper, we further extend this concept from finite faces to all faces (including the infinite face) as follows: A face $s$ (finite or infinite) of a 2-connected plane bipartite graph $G$ is called a forcing face if the subgraph $G?V\left(s\right)$ obtained by removing all vertices of $s$ together with their incident edges has exactly one perfect matching.For a plane elementary bipartite graph $G$ with more than two vertices, we give three necessary and sufficient conditions for $G$ to have all faces forcing. We also give a new necessary and sufficient condition for a finite face of $G$ to be forcing in terms of bridges in the $Z$-transformation graph $Z\left(G\right)$ of $G$. Moreover, for the graphs $G$ whose faces are all forcing, we obtain a characterization of forcing edges in $G$ by using the notion of $handle$, from which a simple counting formula for the number of forcing edges follows.     

Toll convexity

A walk $W$ between two non-adjacent vertices in a graph $G$ is called tolled if the first vertex of $W$ is among vertices from $W$ adjacent only to the second vertex of $W$, and the last vertex of $W$ is among vertices from $W$ adjacent only to the second-last vertex of $W$. In the resulting interval convexity, a set $S\subset V\left(G\right)$ is toll convex if for any two non-adjacent vertices $x,y\in S$ any vertex in a tolled walk between $x$ and $y$ is also in $S$. The main result of the paper is that a graph is a convex geometry (i.e. satisfies the Minkowski–Krein–Milman property stating that any convex subset is the convex hull of its extreme vertices) with respect to toll convexity if and only if it is an interval graph. Furthermore, some well-known types of invariants are studied with respect to toll convexity, and toll convex sets in three standard graph products are completely described.     

Propagation time for zero forcing on a graph

Zero forcing (also called graph infection) on a simple, undirected graph $G$ is based on the color-change rule: if each vertex of $G$ is colored either white or black, and vertex $v$ is a black vertex with only one white neighbor $w$, then change the color of $w$ to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set $B$ of graph $G$ is the minimum number of steps that it takes to force all the vertices of $G$ black, starting with the vertices in $B$ black and performing independent forces simultaneously. The minimum and maximum propagation times of a graph are taken over all minimum zero forcing sets of the graph. It is shown that a connected graph of order at least two has more than one minimum zero forcing set realizing minimum propagation time. Graphs $G$ having extreme minimum propagation times $\left|G\right|?1$, $\left|G\right|?2$, and $0$ are characterized, and results regarding graphs having minimum propagation time 1 are established. It is shown that the diameter is an upper bound for maximum propagation time for a tree, but in general propagation time and diameter of a graph are not comparable.     

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.     

Reconfiguration graphs of shortest paths

For a graph $G$ and$a,b\in V\left(G\right)$, the shortest path reconfiguration graph of $G$ with respect to $a$ and$b$ is denoted by $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths between $a$ and$b$ in $G$. Two vertices in $V\left(S(G,a,b)\right)$ are adjacent, if their corresponding paths in $G$ differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.     

Edge proximity and matching extension in punctured planar triangulations

A matching $M$ in a graph $G$ is said to be extendable if there exists a perfect matching of $G$ containing $M$. In 1989, it was shown that every connected planar graph with at least $8$ vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is $5$-connected planar triangulation or $5$-connected plane graphs with few non-triangular faces.In this paper, we prove that if $G$ is a $5$-connected plane graph of even order in which at most two faces are not triangular and $M$ is a matching of size four in which the edges lie pairwise distance at least three apart, then $M$ is extendable. A related result concerning perfect matching with proscribed edges is shown as well.     

Location-domination in line graphs

A set $D$ of vertices of a graph $G$ is locating if every two distinct vertices outside $D$ have distinct neighbors in $D$; that is, for distinct vertices $u$ and $v$ outside $D$, $N\left(u\right)\cap D\ne N\left(v\right)\cap D$, where $N\left(u\right)$ denotes the open neighborhood of $u$. If $D$ is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of $G$. A graph $G$ is twin-free if every two distinct vertices of $G$ have distinct open and closed neighborhoods. It is conjectured (Garijo et al., 2014 [15]) and (Foucaud and Henning, 2016 [12]) respectively, that any twin-free graph $G$ without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds.     

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

Constructing connected bicritical graphs with edge-connectivity 2

A graph $G$ is said to be bicritical if the removal of any pair of vertices decreases the domination number of $G$. For a bicritical graph $G$ with the domination number $t$, we say that $G$ is $t$-bicritical. Let $\lambda \left(G\right)$ denote the edge-connectivity of $G$. In [2], Brigham et al. (2005) posed the following question: If $G$ is a connected bicritical graph, is it true that $\lambda \left(G\right)\ge 3?$In this paper, we give a negative answer toward this question; namely, we give a construction of infinitely many connected $t$-bicritical graphs with edge-connectivity $2$ for every integer $t\ge 5$. Furthermore, we give some sufficient conditions for a connected $5$-bicritical graph to have $\lambda \left(G\right)\ge 3$.     

On the unimodality of independence polynomials of very well-covered graphs

The independence polynomial $i(G,x)$ of a graph $G$ is the generating function of the numbers of independent sets of each size. A graph of order $n$ is very well-covered if every maximal independent set has size $n∕2$. Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials.