The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Undirected simple connected graphs with minimum number of spanning trees

We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph L_n,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009].     

On Family of Graphs with Minimum Number of Spanning Trees

We show that there is a well-defined family of connected simple graphs Λ(n, m) on n vertices and m edges such that all graphs in Λ(n, m) have the same number of spanning trees, and if ${G \in \Lambda(n, m)}$ then the number of spanning trees in G is strictly less than the number of spanning trees in any other connected simple graph ${H, H \notin \Lambda(n, m)}$ , on n vertices and m edges.     

Maximality of the signless Laplacian energy

We study the problem of determining the graph with $n$ vertices having largest signless Laplacian energy. We conjecture it is the complete split graph whose independent set has (roughly) $2n∕3$ vertices. We show that the conjecture is true for several classes of graphs. In particular, the conjecture holds for the set of all complete split graphs of order $n$, for trees, for unicyclic and bicyclic graphs. We also give conditions on the number of edges, number of cycles and number of small eigenvalues so the graph satisfies the conjecture.     

Accessibility and Reliability for Connected Bipartite Graphs

In the recently published atlas of graphs [9] the general listing of graphs with diagrams went up to V=7 vertices but the special listing for connected bipartite graphs carried further up to V=8. In this paper we wish to study the random accessibility of these connected bipartite graphs by means of random walks on the graphs using the degree of the gratis starting point as a weighting factor. The accessibility is then related to the concept of reliability of the graphs with only edge failures. Exact expectation results for accessibility are given for any complete connected bipartite graph N₁ cbp N₂ (where cbp denotes connected bipartite) for several values of J (the number of new vertices searched for). The main conjecture in this paper is that for any complete connected bipartite graph N₁ cbp N₂: if |N₁–N₂| 1, then the graph is both uniformly optimal in reliability and optimal in random accessibility within its family. Numerical results are provided to support the conjecture.     

Proper connection number of bipartite graphs

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.     

A Class of Edge Critical 4-Chromatic Graphs

We consider several constructions of edge critical 4-chromatic graphs which can be written as the union of a bipartite graph and a matching. In particular we construct such a graph G with each of the following properties: G can be contracted to a given critical 4-chromatic graph; for each n ≥ 7, G has n vertices and three matching edges (it is also shown that such graphs must have at least \({{8n} \over 5}\) edges); G has arbitrary large girth.     

On the Maximum Weight of a Sparse Connected Graph of Given Order and Size

The weight of an edge of a graph is defined to be the sum of degrees of vertices incident to the edge. The weight of a graph G is the minimum of weights of edges of G. Jendrol’ and Schiermeyer (Combinatorica 21:351–359, 2001) determined the maximum weight of a graph having n vertices and m edges, thus solving a problem posed in 1990 by Erd?s. The present paper is concerned with a modification of the mentioned problem, in which involved graphs are connected and of size \(m\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) -\left( {\begin{array}{c}\lceil n/2\rceil \\ 2\end{array}}\right) \).     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

A quadratic programming approach to the Randić index

Let G(k, n) be the set of connected graphs without multiple edges or loops which have n vertices and the minimum degree of vertices is k. The Randi? index χ = χ(G) of a graph G   is defined by χ(G)=_∑(uv)(_δuδv)^-1/2$\chi (G)={\sum }_{(\mathit{uv})}({\delta }_u{\delta }_v{)}^{-1/2}$, where δ_u is the degree of vertex u and the summation extends over all edges (uv) of G. Caporossi et al. [G. Caporossi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs IV: Chemical trees with extremal connectivity index, Computers and Chemistry 23 (1999) 469–477] proposed the use of linear programming as one of the tools for finding the extremal graphs. In this paper we introduce a new approach based on quadratic programming for finding the extremal graphs in G(k, n) for this index. We found the extremal graphs or gave good bounds for this index when the number n_k of vertices of degree k is between n − k and n. We also tried to find the graphs for which the Randi? index attained its minimum value with given k (k ? n/2) and n. We have solved this problem partially, that is, we have showed that the extremal graphs must have the number n_k of vertices of degree k less or equal n − k and the number of vertices of degree n − 1 less or equal k.     

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.     

On the Nullity of Bipartite Graphs

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. We obtain some lower bounds for the nullity of graphs and we then find the nullity of bipartite graphs with no cycle of length a multiple of 4 as a subgraph. Among bipartite graphs on n vertices, the star has the greatest nullity (equal to n − 2). We generalize this by showing that among bipartite graphs with n vertices, e edges and maximum degree Δ which do not have any cycle of length a multiple of 4 as a subgraph, the greatest nullity is . G. R. Omidi: This research was in part supported by a grant from IPM (No.87050016).     

Generating 3-vertex connected spanning subgraphs

In this paper we present an algorithm to generate all minimal 3-vertex connected spanning subgraphs of an undirected graph with n vertices and m edges in incremental polynomial time, i.e., for every K we can generate K (or all) minimal 3-vertex connected spanning subgraphs of a given graph in O(K²log(K)m²+K²m³) time, where n and m are the number of vertices and edges of the input graph, respectively. This is an improvement over what was previously available and is the same as the best known running time for generating 2-vertex connected spanning subgraphs. Our result is obtained by applying the decomposition theory of 2-vertex connected graphs to the graphs obtained from minimal 3-vertex connected graphs by removing a single edge.     

Strong chromatic index of subset graphs

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S_m(k, l) is a bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. We show that and that this number satisfies the strong chromatic index conjecture by Brualdi and Quinn for bipartite graphs. Further, we demonstrate that the conjecture is also valid for a more general family of bipartite graphs. © 1997 John Wiley & Sons, Inc.     

On a conjecture of the Randi? index

The Randi? index of a graph G is defined as , where d(u) is the degree of vertex u and the summation goes over all pairs of adjacent vertices u, v. A conjecture on R(G) for connected graph G is as follows: R(G)≥r(G)−1, where r(G) denotes the radius of G. We proved that the conjecture is true for biregular graphs, connected graphs with order n≤10 and tricyclic graphs.     

An extremal problem in graph theory

It is proved that the maximum number of cut-vertices in a connected graph withn vertices andm edges is $$max\left\{ {q:m \leqq (_2^{n - q} ) + q} \right\}$$ All the extremal graphs are determined and the corresponding problem for cut-edges is also solved.     

Enumeration of Bipartite Self-Complementary Graphs

Let e(m, n), o(m, n), bsc(m, n) be the number of unlabelled bipartite graphs with an even number of edges whose partite sets have m vertices and n vertices, the number of those with an odd number of edges, and the number of unlabelled bipartite self-complementary graphs whose partite sets have m vertices and n vertices, respectively. Then this paper shows that the equality bsc(m, n) = e(m, n) ? o(m, n) holds.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.