Determining the size of a maximum independent set of a graph \(G\), denoted by \(\alpha(G)\), is an NP-hard problem. Therefore, many attempts are made to find upper and lower bounds, or exact values of \(\alpha(G)\) for special classes of graphs. This paper is aimed towards studying this problem for the class of generalized Petersen graphs. We find new upper and lower bounds and some exact values for \(\alpha(P(n,k))\). With a computer program, we have obtained exact values for each \(n 2k\). We prove this conjecture for some cases. In particular, we show that if \(n > 3k\), the conjecture is valid. We checked the conjecture with our table for \(n < 78\) and found no inconsistency. Finally, we show that for every fixed \(k\), \(\alpha(P(n,k))\) can be computed using an algorithm with running time \(O(n)\).

In this paper we give the solutions of finding maximum packings and minimum coverings of \(\lambda\)-fold complete symmetric digraphs with \(6\)-circuits.

In recent researches on a discriminant for polynomials, I faced a recursive (combinatorial) sequence \(\lambda_{n,m}\) whose first four terms and identities are \(\lambda_{0,m} := \binom{m}{0}\), \(\lambda_{1,m} := \binom{m}{1}=\binom{m}{m-1}\), \(\lambda_{2,m} := {\binom{m}{2}}^2 – \binom{m}{2}=\binom{m+1}{m-1}\), and \(\lambda_{3,m} = {\binom{m}{1}}^3 – 2\binom{m}{1}\binom{m}{2} + \binom{m}{3}=\binom{m+2}{m-1}\). In this paper, I introduce this sequence, prove an identity concerning it, and leave a problem and a conjecture regarding its properties.

Let \(\mu_1, \mu_2, \ldots, \mu_n\) be the eigenvalues of the sum-connectivity matrix of a graph \(G\). The sum-connectivity spectral radius of \(G\) is the largest eigenvalue of its sum-connectivity matrix, and the sum-connectivity Estrada index of \(G\) is defined as \(\mathrm{SEE}(G) = \sum_{i=1}^{n} e^{\mu_i}\). In this paper, we obtain some results about the sum-connectivity spectral radius of graphs. In addition, we give some upper and lower bounds on the sum-connectivity Estrada index of graph \(G\), as well as some relations between \(\mathrm{SEE}\) and sum-connectivity energy. Moreover, we characterize that the star has maximum sum-connectivity Estrada index among trees on \(n\) vertices.

Let \(G(n;\theta_{2k+1})\) denote the class of non-bipartite graphs on \(n\) vertices containing no \(\theta_{2k+1}\)-graph and let \(f(n; \theta_{2k+1}) = \max\{\varepsilon(G) : G \in \mathcal{G}(n;\theta_{2k+1})\}\). In this paper, we determine \(f(n; 0_5)\), by proving that for \(n \geq 11\), \(f(n; 0_5) \leq \lfloor\frac{(n-1)^2}{4}\rfloor + 1\). Further, the bound is best possible. Our result confirms the validity of the conjecture made in [1], “Some extremal problems in graph theory”, Ph.D. thesis, Curtin University of Technology, Australia (2007).

Let \(G\) be a cactus, where all blocks of \(G\) are either edges or cycles. Denote \(\mathcal{G}(n,r)\) the set of cactuses of order \(n\) and with \(r\) cycles. In this paper, we present a unified approach to the extremal cactuses for the Schultz and the modified Schultz indices.

In this paper, I study the Eulerian numbers \((A(m,k))_{k=1}^{m}\) and prove the relationship between \(\sum_{i=1}^{n}{i^m}\) and \((A(m,k))_{k=1}^{m}\), to be \(\sum_{i=1}^{n}{i^m} = \sum_{k=1}^m A(m,k)\binom{m+k}{m+1}\).

An \((s, t)\)-spread in a finite vector space \(V = V(n, q)\) is a collection \(\mathcal{F}\) of \(t\)-dimensional subspaces of \(V\) with the property that every \(s\)-dimensional subspace of \(V\) is contained in exactly one member of \(F\). It is remarkable that no \((s, t)\)-spreads have been found yet, except in the case \(s = 1\).
In this note, the concept of an \(\alpha\)-point to a \((2,3)\)-spread \(\mathcal{F}\) in \(V = V(7,2)\) is introduced. A classical result of Thomas, applied to the vector space \(V\), states that all points of \(V\) cannot be \(\alpha\)-points to a given \((2,3)\)-spread \(\mathcal{F}\) in \(V\). In this note, we strengthen this result by proving that every \(6\)-dimensional subspace of \(V\) must contain at least one point that is not an \(\alpha\)-point to a given \((2, 3)\)-spread.

We construct explicitly the automorphism group of the folded hypercube \(FQ_n\) of dimension \(n > 3\), as a semidirect product of \(N\) by \(M\), where \(N\) is isomorphic to the Abelian group \(\mathbb{Z}_2^{n}\), and \(M\) is isomorphic to \(\mathrm{Sym}(n+1)\), the symmetric group of degree \(n+1\). Then, we will show that the folded hypercube \(FQ_n\) is a symmetric graph.

The Merrifield-Simmons index \(\sigma(G)\) of a graph \(G\) is defined as the number of subsets of the vertex set, in which any two vertices are non-adjacent, i.e., the number of independent vertex sets of \(G\). A tree is called an \(r\)-leaf tree if it contains \(r\) vertices with degree one. In this paper, we obtain the smallest Merrifield-Simmons index among all trees with \(n\) vertices and exactly six leaves, and characterize the corresponding extremal graph.