Let \(G\) be a simple undirected graph. Denote by \(mi(G)\) the number of maximal independent sets in \(G\). In this paper, we determine the second and third largest number of maximal independent sets in trees. Extremal trees achieving these values are also determined.

In \([5]\), the first author posed the problem of determining the spectrum of \((K_4, K_4 – e)\)-designs. In this article, we solve this problem, and also determine the spectrum of \((K_4, K_4 – e)\)-designs with exactly one \(K_4\) (or, equivalently, the spectrum of \((K_4 – e)\)-designs with a hole of size \(4\)). We also improve the bound for embedding a partial \(S(2,4,v)\) into a \((K_4, K_4 – e)\)-design given in \([5]\).

Given a digraph \(D\), its competition graph \(C(D)\) has the same vertex set as \(D\) and an edge between two vertices \(x\) and \(y\) if there is a vertex \(u\) so that \((x,u)\) and \((y,u)\) are arcs of \(D\). Motivated by a problem of communications, Kim and Roberts [2002] studied the competition graphs of the special digraphs known as semiorders and the graphs arising as competition graphs of acyclic digraphs satisfying conditions so called \(C(p)\) or \(C^*(p)\). While they could completely characterize the competition graph of an acyclic digraph satisfying \(C(p)\), they obtained only partial results on \(C^*(p)\) and left the general case open. In this paper, we answer their open question.

A graph \(G\) is said to be well-covered if every maximal independent set of \(G\) is of the same size. It has been shown that characterizing well-covered graphs is a co-NP-complete problem. In an effort to characterize some of these graphs, different subclasses of well-covered graphs have been studied. In this paper, we will introduce the subclass of stable well-covered graphs, which are well-covered graphs that remain well-covered with the addition of any edge. Some properties of stable well-covered graphs are given. In addition, the relationships between stable well-covered graphs and some other subclasses of well-covered graphs, including the surprising equivalence between stable well-covered graphs and other known subclasses, are proved.

Let \(G\) be a graph with vertex set \(V(G)\). For any \(S \subseteq V(G)\), we use \(w(G – S)\) to denote the number of components of \(G – S\). The toughness of \(G\), \(t(G)\), is defined as \(t(G) = \min\left\{\frac{|S|}{w(G – S)} \mid S \subseteq V(G), w(G – S) > 1\right\}\) if \(G\) is not complete; otherwise, set \(t(G) = +\infty\). In this paper, we consider the relationship between the toughness and the existence of fractional \((g, f)\)-factors. It is proved that a graph \(G\) has a fractional \((g, f)\)-factor if \(t(G) \geq \frac{b^2 – 1}{a}\).

An almost-bipartite graph is a non-bipartite graph with the property that the removal of a particular single edge renders the graph bipartite. A graph labeling of an almost-bipartite graph \(G\) with \(n\) edges that yields cyclic \(G\)-decompositions of the complete graph \(K_{2nt+1}\) (i.e., cyclic \((K_{2nt+1}, G)\)-designs) was recently introduced by Blinco, El-Zanati, and Vanden Eynden. They called such a labeling a \(\gamma\)-labeling. Here we show that the class of almost-bipartite graphs obtained from \(C_m\) by adding an edge joining distinct vertices in the same part in the bipartition of \(V(C_{2m})\) has a \(\gamma\)-labeling if and only if \(m \geq 3\). This, along with results of Blinco and of Froncek, shows that if \(G\) is a graph of size \(n\) consisting of a cycle with a chord, then there exists a cyclic \((K_{2nt+1},G)\)-design for every positive integer \(t\).

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 is a realization of \(\pi\) containing \(H\) as a subgraph. In this paper, we characterize potentially \(K_{1,1,6}\)-positive graphic sequences. This characterization implies the value of \(\sigma(K_{1,1,6}, n)\). Moreover, we also give a simple sufficient condition for a positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) to be potentially \(K_{1,1,s}\)-graphic for \(n \geq s+2\) and \(s \geq 2\).

Let \(H(B)\) denote the space of all holomorphic functions on the unit ball \(B\). Let \(u \in H(B)\) and \(\varphi\) be a holomorphic self-map of \(B\). This paper characterizes the boundedness and compactness of the weighted composition operator \(uC_{\varphi}\), from Bloch-type spaces to weighted-type spaces in the unit ball.

Let \(G\) be a graph of order \(n\). Let \(a\) and \(b\) be integers with \(1 \leq a < b\), and let \(k \geq 2\) be a positive integer not larger than the independence number of \(G\). Let \(g(x)\) and \(f(x)\) be two non-negative integer-valued functions defined on \(V(G)\) such that \(a \leq g(x) \frac{(a+b)(k(a+b)-2)}{a+1}\) and \(|N_G(x_1) \cup N_G(x_2) \cup \cdots \cup N_G(x_k)| \geq \frac{(b-1)n}{a+b}\) for any independent subset \(\{x_1, x_2, \ldots, x_k\}\) of \(V(G)\). Furthermore, we show that the result is best possible in some sense.

A graph \(G\) is called quasi-claw-free if it satisfies the property:\(d(x,y) = 2 \Rightarrow \text{there exists} u \in N(x) \cap N(y) \text{ such that } N[u] \subseteq N[x] \cup N[y].\) It is shown that a Hamiltonian cycle can be found in polynomial time in four subfamilies of quasi-claw-free graphs.