Sharp upper bounds on the second largest eigenvalues of connected graphs

Let ${\lambda }_2$ be the second largest eigenvalue of a graph. Powers (1988) [4] gave some upper bounds of ${\lambda }_2$ for general graphs and bipartite graphs, respectively. Considering that these bounds are not always attainable for connected graphs, we present sharp upper bounds of ${\lambda }_2$ for connected graphs and connected bipartite graphs in this paper. Moreover, the extremal graphs are completely characterized.     

Connected matchings in chordal bipartite graphs

A connected matching in a graph is a collection of edges that are pairwise disjoint but joined by another edge of the graph. Motivated by applications to Hadwiger’s conjecture, Plummer, Stiebitz, and Toft (2003) introduced connected matchings and proved that, given a positive integer $k$, determining whether a graph has a connected matching of size at least $k$ is NP-complete. Cameron (2003) proved that this problem remains NP-complete on bipartite graphs, but can be solved in polynomial-time on chordal graphs. We present a polynomial-time algorithm that finds a maximum connected matching in a chordal bipartite graph. This includes a novel edge-without-vertex-elimination ordering of independent interest. We give several applications of the algorithm, including computing the Hadwiger number of a chordal bipartite graph, solving the unit-time bipartite margin-shop scheduling problem in the case in which the bipartite complement of the precedence graph is chordal bipartite, and determining–in a totally balanced binary matrix–the largest size of a square sub-matrix that is permutation equivalent to a matrix with all zero entries above the main diagonal.     

Some graphs whose second largest eigenvalue does not exceed 2

We determine all trees whose second largest eigenvalue does not exceed $\sqrt{2}$. Next, we consider two classes of bipartite graphs, regular and semiregular, with small number of distinct eigenvalues. For all graphs considered we determine those whose second largest eigenvalue is equal to $\sqrt{2}$. Some additional results are also given.     

Algebraic characterizations of regularity properties in bipartite graphs

Regular and distance-regular characterizations of general graphs are well-known. In particular, the spectral excess theorem states that a connected graph Γ$\Gamma$ is distance-regular if and only if its spectral excess (a number that can be computed from the spectrum) equals the average excess (the mean of the numbers of vertices at extremal distance from every vertex). The aim of this paper is to derive new characterizations of regularity and distance-regularity for the more restricted family of bipartite graphs. In this case, some characterizations of (bi)regular bipartite graphs are given in terms of the mean degrees in every partite set and the Hoffman polynomial. Moreover, it is shown that the conditions for having distance-regularity in such graphs can be relaxed when compared with general graphs. Finally, a new version of the spectral excess theorem for bipartite graphs is presented.     

The graph grabbing game on Km,n-trees

The graph grabbing game is a two-player game on weighted connected graphs where all weights are non-negative. Two players, Alice and Bob, alternately remove a non-cut vertex from the graph (i.e., the resulting graph is still connected) and get the weight assigned to the vertex, where the starting player is Alice. Each player’s aim is to maximize his/her outcome when all vertices have been taken, and Alice wins the game if she gathered at least half of the total weight. Seacrest and Seacrest (2017) proved that Alice has a winning strategy for every weighted tree with even order, and conjectured that the same statement holds for every weighted connected bipartite graph with even order. In this paper, we prove that Alice wins the game on a type of a connected bipartite graph with even order called a $K_{m,n}$-tree.     

Spectral radius of strongly connected digraphs

Let $D$ be a digraph with vertex set $V\left(D\right)$ and $A$ be the adjacency matrix of $D$. The largest eigenvalue of $A$, denoted by $\rho \left(D\right)$, is called the spectral radius of the digraph $D$. In this paper, we establish some sharp upper or lower bounds for digraphs with some given graph parameters, such as clique number, girth, and vertex connectivity, and characterize the corresponding extremal graphs. In addition, we give the exact value of the spectral radii of those digraphs.     

Max-cut and extendability of matchings in distance-regular graphs

A connected graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is $1$-extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter $D\ge 3$ are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency $k\ge 3$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency $k$ grows linearly in $k$. We conjecture that the extendability of a distance-regular graph of even order and valency $k$ is at least $\lceil k/2\rceil -1$ and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters.     

On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let $K_4$ and $K_{1,3}$ (claw) denote the complete (bipartite) graph on 4 and $1+3$ vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a $K_4$-free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, $K_4$)-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for $K_4$-free planar graphs with maximum degree five.     

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.     

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.     

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.     

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