A set system is called t-intersecting if every two members meet each other in at least t elements. Katona determined the minimum ratio of the shadow and the size of such families and showed that the Erdős-Ko-Rado theorem immediately follows from this result. The aim of this note is to reproduce the proof to obtain a slight improvement in the Kneser graph. We also give a brief overview of corresponding results.

Let $\alpha \left(n\right)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n\ge 3$ spanning trees. Similarly, define $\beta \left(n\right)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n\ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha \left(n\right),\beta \left(n\right)\le n$. In this paper, we show that $\alpha \left(n\right)\le \frac{1}{3}(n+4)$ and $\beta \left(n\right)\le \frac{1}{3}(n+7)$ if and only if $n\notin \{3,4,5,6,7,9,10,13,18,22\}$, which is a subset of Euler’s idoneal numbers. Moreover, if $n\neg \equiv 2(mod3)$ and $n\ne 25$ we show that $\alpha \left(n\right)\le \frac{1}{4}(n+9)$ and $\beta \left(n\right)\le \frac{1}{4}(n+13).$ This improves some previously estabilished bounds.

The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.

Given integers p > k > 0, we consider the following problem of extremal graph theory: How many edges can a bipartite graph of order 2p have, if it contains a unique k-factor? We show that a labeling of the vertices in each part exists, such that at each vertex the indices of its neighbours in the factor are either all greater or all smaller than those of its neighbours in the graph without the factor. This enables us to prove that every bipartite graph with a unique k-factor and maximal size...

Gutman and Wagner proposed the concept of the matching energy which is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph. And they pointed out that the chemical applications of matching energy go back to the 1970s. Let T be a tree with n vertices. In this paper, we characterize the trees whose complements have the maximal, second-maximal and minimal matching energy. Furthermore, we determine the trees with edge-independence number p whose complements have...

Let C denote the claw $K_{1,3}$, N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and $Z_i$ the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does...

The distance spectral radius ρ(G) of a graph G is the largest eigenvalue of the distance matrix D(G). Let U (n,m) be the class of unicyclic graphs of order n with given matching number m (m ≠ 3). In this paper, we determine the extremal unicyclic graph which has minimal distance spectral radius in U (n,m) Cn.

For two vertices $u$ and $v$ of a graph $G$, the closed interval $I[u,v]$ consists of $u$, $v$, and all vertices lying in some $u\text{--}v$ geodesic of $G$, while for $S\subseteq V\left(G\right)$, the set $I\left[S\right]$ is the union of all sets $I[u,v]$ for $u,v\in S$. A set $S$ of vertices of $G$ for which $I\left[S\right]=V\left(G\right)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g\left(G\right)$. A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $\mathrm{e}x\left(G\right)$. A graph $G$ is an extreme geodesic...