For two vertices \(u\) and \(v\) in a strong digraph \(D\), the strong distance between \(u\) and \(v\) is the minimum number of arcs of a strong subdigraph of \(D\) containing \(u\) and \(v\). The strong eccentricity of a vertex \(v\) of \(D\) is the strong distance between \(v\) and a vertex farthest from \(v\). The strong diameter (strong radius) of \(D\) is the maximum (minimum) strong eccentricity among all vertices of \(D\). The lower orientable strong diameter (lower orientable strong radius), \(\mathrm{sdiam}(G)\) (\(\mathrm{srad}(G)\)), of a 2-edge-connected graph \(G\) is the minimum strong diameter (minimum strong radius) over all strong orientations of \(G\). In this paper, a conjecture of Chen and Guo is disproved by proving \(\mathrm{sdiam}(K_{3} \square K_{3}) = \mathrm{sdiam}(K_{3} \square K_{4}) = 5\), \(\mathrm{sdiam}(K_{m} \square P_{n})\) is determined, \(\mathrm{sdiam}(G)\) and \(\mathrm{srad}(G)\) for cycle vertex multiplications are computed, and some results concerning \(\mathrm{sdiam}(G)\) are described.

The aim of this note is to present a short proof of a result of Alaeiyan et al. [Bull. Austral. Math. Soc.\( 77 (2008) 315-323;\)
Proc. Indian Acad. Sci., Math. Sci. \(119 (2009) 647-653\)] concerning the non-existence of cubic semisymmetric graphs of order \(8p\) or \(8p^2\), where \(p\) is a prime. In those two papers, the authors choose the heavy weaponry of covering techniques. Our proof relies on the analysis of the subgroup structure of the full automorphism group of the graph and the normal quotient graph theory.

Let \(G\) be a graph of order \(n\) with adjacency matrix \(A(G)\) and diagonal degree matrix \(D(G)\). The generalized characteristic polynomial of \(G\) is defined to be \(f_G(x,t) = \det (xI_n – (A(G) – tD(G)))\). The \(R\)-graph of \(G\), denoted by \(R(G)\), is obtained by adding a new vertex for each edge of \(G\) and joining each new vertex to both end vertices of the corresponding edge. The generalized \(R\)-vertex corona, denoted by \(R(G) \boxdot \wedge _i^n H\), is the graph obtained from \(R(G)\) and \(H\) by joining the \(i\)-th vertex of \(V(G)\) to every vertex of \(H\). In this paper, we determine the generalized characteristic polynomial of \(R(G) \boxdot \wedge _i^n H\). As applications, we get infinitely many pairs of generalized cospectral graphs, the number of spanning trees and Kirchhoff index of \(R(G) \boxdot\wedge _i^n H\).

In this paper, we introduce an \(O(n^2)\) time algorithm to determine the cyclic edge connectivity of a planar graph, where \(n\) is the order of the planar graph. This is the first correct square time algorithm for cyclic edge connectivity of planar graphs.

Let \(G = (V, E)\), with \(|V| = n\), be a simple connected graph. An edge-colored graph \(G\) is rainbow edge-connected if any two vertices are connected by a path whose edges are colored by distinct colors. The rainbow connection number of a connected graph \(G\), denoted by \(rc(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow edge-connected. In this paper, we obtain tight bounds for \(rc(G)\). We use our results to generalize previous results for graphs with \(\delta(G) \geq 3\).

In this paper, we provide the 4-way combinatorial interpretations of some Rogers–Ramanujan type identities using partitions with “\(n + t\) copies of \(n\)”, lattice paths, \(k\)-partitions, and ordinary partitions.

In this paper, we study the Fibonacci polynomials modulo \(m\) such that \(x^2 = x + 1\) and then we obtain miscellaneous properties of these sequences. Also, we extend the Fibonacci polynomials to the ring of complex numbers. We define the Fibonacci Polynomial-type orbits \(F^R_{(a,b)}(x) = \{x_i\}\), where \(R\) is a 2-generator ring and \((a,b)\) is a generating pair of the ring \(R\). Furthermore, we obtain the periods of the Fibonacci Polynomial-type orbits \(F^R_{(a,b)}(x)\) in finite 2-generator rings of order \(p^2\).

A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order \(n \geq 12\) and size at least\(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint theta graphs. As a corollary, every graph of order \(n \geq 12\) and size at least \(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil ,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint cycles of even length. The lower bound on the size is sharp in general.

A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. A semisymmetric graph must be bipartite whose automorphism group has two orbits of the same size on the vertices. One of our long-term goals is to determine all the semisymmetric graphs of order \(2p^3\), for any prime \(p\). All these graphs \(\Gamma\) with the automorphism group \(Aut(\Gamma)\), are divided into two subclasses: (I) \(Aut(\Gamma)\) acts unfaithfully on at least one bipart; and (II) \(Aut(\Gamma)\) acts faithfully on both biparts. In [9],[19] and [20], a complete classification was given for Subclass (I). In this paper, a partial classification is given for Subclass (II), when \(Aut(\Gamma)\) acts primitively on one bipart.

The notions of \(L\)-tree-coloring and list vertex arboricity of graphs are introduced in the paper, while a sufficient condition for a plane graph admitting an \(L\)-tree-coloring is given. Further, it is proved that every graph without \(K_{5}\)-minors or \(K_{3,3}\)-minors has list vertex arboricity at most \(3\), and this upper bound is sharp.