In this note, we characterize graphs with a given small matching number. Specifically, we characterize graphs with minimum degree at least \(2\) and matching number at most \(3\). The characterization when the matching number is at most \(2\) strengthens the result of Lai and Yan’s that characterized the non-supereulerian \(2\)-edge connected graphs with matching at most \(2\). Furthermore, the characterization of graphs with matching number at most \(3\) addresses a conjecture of Lai and Yan in [SuperEulerian graphs and matchings, Applied Mathematics Letters 24 (2011) 1867-1869].

Let \(D(G)\) be the distance matrix of a connected graph \(G\). The distance spectral radius of \(G\) is the largest eigenvalue of \(D(G)\) and has been proposed as a molecular structure descriptor. In this paper, we study the distance spectral radius of graphs with a given independence number. Special attention is paid to graphs with a given independence number and maximal distance spectral radius.

Key distribution is paramount for Wireless Sensor Networks (WSNs). The design of key management schemes is the most important aspect and basic research field in WSNs. A key distribution scheme based on symplectic geometry over fields is proposed, where a 2-dimensional subspace in symplectic geometry represents a node, and all \(2s\)-dimensional non-isotropic subspaces represent the key pool, guaranteeing that every pair of nodes has a shared key, thus improving network connectivity. The performance analysis shows that the scheme has good connectivity and higher resilience to node compromise compared to other key pre-distribution schemes.

For a given graph \(H\), a graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) is said to be potentially \(H\)-graphic if there exists a realization of \(\pi\) containing \(H\) as a subgraph. Let \(K_{ r+1} – C_k\) be the graph obtained from \(K_{ r+1}\) by removing the \(k\) edges of a \(k\)-cycle. In this paper, we first characterize potentially \(A_{ r+1} – C_k\)-graphic sequences (\(3 \leq k \leq r+1\)), analogous to Yin et al.’s characterization [19], using a system of inequalities. Then, we obtain a sufficient and necessary condition for a graphic sequence \(\pi\) to have a realization containing \(K_{r+1} – C_k\) as an induced subgraph.

A graph \(G\) with \(1 \leq n \leq |V(G)| – 2\) is said to be \(n\)-factor-critical if any \(n\) vertices of \(G\) are deleted, then the resultant graph has a perfect matching. An odd graph \(G\) with \(2k \leq |V(G)| – 3\) is said to be near \(k\)-extendable if \(G\) has a \(k\)-matching and any \(k\)-matching of \(G\) can be extended to a near perfect matching of \(G\). Lou and Yu [Australas. J. Combin. 29 (2004) 127-133] showed that any \(5\)-connected planar odd graph is \(3\)-factor-critical. In this paper, as an improvement of Lou and Yu’s result, we prove that any \(4\)-connected planar odd graph is \(3\)-factor-critical and also near \(2\)-extendable. Furthermore, we prove that all \(5\)-connected planar odd graphs are near \(3\)-extendable.

Determining the biplanar crossing number of the graph \(C_n \times C_n \times C_n \times P_n\) was a problem proposed in a paper by Czabarka, Sykora, Székely, and Vito [2]. We find as a corollary to the main theorem of this paper that the biplanar crossing number of the aforementioned graph is zero. This result follows from the decomposition of \(C_n \times C_n \times C_n \times P_m\) into one copy of \(C_{n^2} \times P_{lm},l-2\) copies of \(C_{n^2} \times P_m\), and a copy of \(C_{n^2} \times P_{2m}\).

Let \(A_n\) be the alternating group of degree \(n\) with \(n \geq 5\). Set \(S = \{(1ij), (1ji) \mid 2 \leq i, j \leq n, i \neq j\}\). In this paper, it is shown that the full automorphism group of the Cayley graph \(\mathrm{Cay}(A_n, S)\) is the semi-product \(R(A_n) \rtimes \mathrm{Aut}(A_n, S)\), where \(R(A_n)\) is the right regular representation of \(A_n\) and \(\mathrm{Aut}(A_n, S) = \{\phi \in \mathrm{Aut}(A_n) \mid S^\phi = S\} \cong \mathrm{S_{n-1}}\).

Topological indices of graphs, and trees in particular, have been vigorously studied in the past decade due to their many applications in different fields. Among such indices, the number of subtrees (BC-subtrees), along with their variations, have received much attention. In this paper, we provide some new evaluation results related to these two indices on specific structures, such as generalized Bethe trees, Bethe trees, and dendrimers, which are of practical interest. Using generating functions, we also examine the asymptotic behavior of subtree (resp. BC-subtree) density of dendrimers.

For an integer \(k \geq 0\), a graphical property \(P\) is said to be \(k\)-stable if whenever \(G + uv\) has property \(P\) and \(d_G(u) + d_G(v) \geq k\), where \(uv \notin E(G)\), then \(G\) itself has property \(P\). In this note, we present spectral sufficient conditions for several stable properties of a graph.

Let \(G\) be a connected graph. The degree resistance distance of \(G\) is defined as \(D_R(G) = \sum\limits_{\{u,v\} \in V(G)} (d(u) + d(v))r(u,v)\), where \(d(u)\) (and \(d(v)\)) is the degree of the vertex \(u\) (and \(v\)), and \(r(u,v)\) is the resistance distance between vertices \(u\) and \(v\). A fully loaded unicyclic graph is a unicyclic graph with the property that there is no vertex with degree less than \(3\) in its unique cycle. In this paper, we determine the minimum and maximum degree resistance distance among all fully loaded unicyclic graphs with \(n\) vertices, and characterize the extremal graphs.