We start by proving that the Henson graphs \(H_n\), \(n \geq 3\) (the homogeneous countable graphs universal for the class of all finite graphs omitting the clique of size \(n\)), are retract rigid. On the other hand, we provide a full characterization of retracts of the complement of \(H_3\). Further, we prove that each countable partial order embeds in the natural order of retractions of the complements of Henson graphs. Finally, we show that graphs omitting sufficiently large null subgraphs omit certain configurations in their endomorphism monoids.

Combining integration method with series rearrangement,we establish several closed formulae for Gauss hypergeometric series with four free parameters, which extend essentially the related results found recently by Elsner \((2005).\)

In this paper, we study the global behavior of the nonnegative equilibrium points of the difference equation

\(x_{n+1} = \frac{Ax_{n-2l}}{B+C \prod\limits_{i=0}^{2k}x_{n-i}}, n=0,1,\ldots ,\)

where \(A\), \(B\), \(C\) are nonnegative parameters, initial conditions are nonnegative real numbers, and \(k\), \(l\) are nonnegative integers, \(l \leq k\). Also, we derive solutions of some special cases of this equation.

In this paper, the critical group structure of the Cartesian product graph \(C_4 \times C_n\) is determined, where \(n \geq 3\).

Let \(G = (V, E)\) be a simple connected graph with \(7\) vertices. The degree of \(v_i \in V\) and the average of degrees of the vertices adjacent to \(v_i\) are denoted by \(d_i\) and \(m_i\), respectively. The spectral radius of \(G\) is denoted by \(\rho(G)\). In this paper, we introduce a parameter into an equation of adjacency matrix, and obtain two inequalities for upper and lower bounds of spectral radius. By assigning different values to this parameter, one can obtain some new and existing results on spectral radius. Specially, if \(G\) is a nonregular graph, then

\[\rho(G) \leq \max_{1 \leq j<i \leq n} \{ \frac{d_i m_i – d_j m_j + \sqrt{(d_i m_i – d_j m_j)^2 – 4d_i d_j(d_i-d_j) (m_i – m_j)}}{2(d_i-d_j)} \}\] and \[\rho(G)\geq \min_{1 \leq j<i \leq n} \{ \frac{d_i m_i – d_j m_j + \sqrt{(d_i m_i – d_j m_j)^2 – 4d_i d_j(d_i-d_j) (m_i – m_j)}}{2(d_i-d_j)} \}.\] If \(G\) is a bidegreed graph whose vertices of same degree have equal average of degrees, then the equality holds.

An orientation of a simple graph \(G\) is called an oriented graph. If \(D\) is an oriented graph, \(\delta(D)\) its minimum degree and \(\lambda(D)\) its edge-connectivity, then \(\lambda(D) \leq \delta(D)\). The oriented graph is called maximally edge-connected if \(\lambda(D) = \delta(D)\) and super-edge-connected, if every minimum edge-cut is trivial. In this paper, we show that an oriented graph \(D\) of order \(n\) without any clique of order \(p + 1\) in its underlying graph is maximally edge-connected when

\[n \leq 4{\lfloor\frac{p\delta(D)}{p – 1}\rfloor}-1.\]

Some related conditions for oriented graphs to be super-edge-connected are also presented.

Denote by \(\mathcal{A_n}\), the set of the polyphenyl chains with \(n\) hexagons. For any \(A_n \in \mathcal{A_n}\), let \(m_k(A_n)\) and \(i_k(A_n)\) be the numbers of \(k\)-matchings and \(k\)-independent sets of \(A_n\), respectively. In the paper, we show that for any \(A_n \in \mathcal{A_n}\) and for any \(k \geq 0\),\(m_k(M_n) \leq m_k(A_n) \leq m_k(O_n) \quad \text{and} \quad i_k(M_n) \geq i_k(A_n) \geq i_k(O_n),\) with the equalities holding if \(A_n = M_n\) or \(A_n = O_n\), where \(M_n\) and \(O_n\) are the meta-chain and the ortho-chain, respectively. These generalize some related results in \([1]\).

Let \(G = (X, Y, E(G))\) be a bipartite graph with vertex set \(V(G) = X ! Y\) and edge set \(E(G)\), and let \(g, f\) be two nonnegative integer-valued functions defined on \(V(G)\) such that \(g(x) \leq f(x)\) for each \(x \in V(G)\). A \((g, f)\)-factor of \(G\) is a spanning subgraph \(F\) of \(G\) such that \(g(x) \leq d_F(x) \leq f(x)\) for each \(x \in V(F)\); a \((g, f)\)-factorization of \(G\) is a partition of \(E(G)\) into edge-disjoint \((g, f)\)-factors. Let \(\mathcal{F} = \{F_1, F_2, \ldots, F_m\}\) be a factorization of \(G\) and \(H\) be a subgraph of \(G\) with \(m\) edges. If \(F_i\), \(1 \leq i \leq m\), has exactly \(r\) edges in common with \(H\), we say that \(F_i\) is \(r\)-orthogonal to \(H\). In this paper, it is proved that every bipartite \((0, mf-(m-1)r)\)-graph has \((0, f)\)-factorizations randomly \(r\)-orthogonal to any given subgraph with \(m\) edges if \(2r \leq f(x)\) for any \(x \in V(G)\).

We define an \(r\)-capacitated dominating set of a graph \(G = (V,E)\) as a set \(\{v_1, \ldots, v_k\} \subseteq V\) such that there is a partition \((V_1, \ldots, V_k)\) of \(V\) where for all \(i\), \( v_i \in V_i\), \(v_i\) is adjacent to all of \(V_i – \{v_i\}\), and \(|V_i| \leq r + 1\). \(\daleth_r(G)\) is the minimum cardinality of an \(r\)-capacitated dominating set. We show properties of \(\daleth_r\), especially as regards the trivial lower bound \(|V|/(r + 1)\). We calculate the value of the parameter in several graph families, and show that it is related to codes and polyominoes. The parameter is \(NP\)-complete in general to compute, but a greedy approach provides a linear-time algorithm for trees.

On the basis of joint trees introduced by Yanpei Liu, by choosing different spanning trees and classifying the associated surfaces, we obtain the explicit expressions of genus polynomials for three types of graphs, namely \(K_5^n, W_6^n\) and \(K_{3,3}^n\), which are different from the graphs whose embedding distributions by genus have been obtained. And \(K_5^n\) and \(K_{3,3}^n\) are non-planar.