Let $G$ be a finite group. The main supergraph $𝒮\left(G\right)$ is a graph with vertex set $G$ in which two vertices $x$ and $y$ are adjacent if and only if $o\left(x\right)\mid o\left(y\right)$ or $o\left(y\right)\mid o\left(x\right)$. In this paper, we will show that $G{\cong }^2{G}_2\left(3^{2n+1}\right)$ if and only if $𝒮\left(G\right)\cong 𝒮{(}^2{G}_2\left(3^{2n+1}\right))$. As a main consequence of our result we conclude that Thompson’s problem is true for the small Ree group ${}^2{G}_2\left(3^{2n+1}\right)$.

We give a graph theoretic interpretation of $r$-Lah numbers, namely, we show that the $r$-Lah number ${⌊\genfrac{}{}{0pt}{}{n}{k}⌋}_r$ counting the number of $r$-partitions of an $(n+r)$-element set into $k+r$ ordered blocks is just equal to the number of matchings consisting of $n-k$ edges in the complete bipartite graph with partite sets of cardinality $n$ and $n+2r-1$ ($0\le k\le n$, $r\ge 1$). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for $r$-Stirling numbers of the second kind. ...

Let $ex(n,G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_i$ denote a path consisting of $i$ vertices and let $m{P}_i$ denote $m$ disjoint copies of $P_i$. In this paper we count $ex(n,3P_4)$.

Let X be a Polish space, and let C₀ and C₁ be disjoint coanalytic subsets of X. The pair (C₀,C₁) is said to be complete if for every pair (D₀,D₁) of disjoint coanalytic subsets of ${\omega }^{\omega }$ there exists a continuous function $f:{\omega }^{\omega }\to X$ such that $f^{-1}\left(C₀\right)=D₀$ and $f^{-1}\left(C₁\right)=D₁$. We give several explicit examples of complete pairs of coanalytic sets.

Let $G$ be a finite group. The main supergraph $𝒮\left(G\right)$ is a graph with vertex set $G$ in which two vertices $x$ and $y$ are adjacent if and only if $o\left(x\right)\mid o\left(y\right)$ or $o\left(y\right)\mid o\left(x\right)$. In this paper, we will show that $G\cong Sz\left(q\right)$ if and only if $𝒮\left(G\right)\cong 𝒮\left(Sz\right(q\left)\right)$, where $q=2^{2m+1}\ge 8$.

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let $G$ be a bridgeless simple graph with minimum degree at least $3$. Jackson and Yoshimoto (2007) showed that $G$ has an even factor containing two arbitrary prescribed edges. They also proved that $G$ has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges $e_1$ and $e_2$ of $G$, there is an even factor containing $e_1$ and $e_2$...

A graph $G$ is $H$-saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$. The saturation number, $\mathrm{sat}(n,H)$, is the minimum number of edges of a graph in the set of all $H$-saturated graphs of order $n$. We determine the saturation number $\mathrm{sat}(n,P_6+t{P}_2)$ for $n\ge \frac{10}{3}t+10$ and characterize the extremal graphs for $n>\frac{10}{3}t+20$.

The generalized $k$-connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as ${\lambda }_k\left(G\right)=min\{\lambda \left(S\right):S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$, where $\lambda \left(S\right)$ denotes the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $S\subseteq V\left(T_i\right)$ for $1\le i\le \ell$. In this paper we prove that for any two connected graphs $G$ and $H$ we have ${\lambda }_3(G\square H)\ge {\lambda }_3\left(G\right)+{\lambda }_3\left(H\right)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also...

Let $G$ be a simple connected graph with vertex set $V\left(G\right)=\{v_1,v_2,\cdots ,v_n\}$ and edge set $E\left(G\right)$, and let $d_{v_i}$ be the degree of the vertex $v_i$. Let $D\left(G\right)$ be the distance matrix and let $T_r\left(G\right)$ be the diagonal matrix of the vertex transmissions of $G$. The generalized distance matrix of $G$ is defined as $D_{\alpha }\left(G\right)=\alpha T_r\left(G\right)+(1-\alpha )D\left(G\right)$, where $0\le \alpha \le 1$. Let ${\lambda }_1\left(D_{\alpha }\left(G\right)\right)\ge {\lambda }_2\left(D_{\alpha }\left(G\right)\right)\ge ...\ge {\lambda }_n\left(D_{\alpha }\left(G\right)\right)$ be the generalized distance eigenvalues of $G$, and let $k$ be an integer with $1\le k\le n$. We denote by $S_k\left(D_{\alpha }\left(G\right)\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)+{\lambda }_2\left(D_{\alpha }\left(G\right)\right)+...+{\lambda }_k\left(D_{\alpha }\left(G\right)\right)$ the sum of the $k$ largest generalized distance eigenvalues. The generalized distance spread of a graph $G$ is defined as $D_{\alpha }S\left(G\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)-{\lambda }_n\left(D_{\alpha }\left(G\right)\right)$....

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. Parsons gave a recursive formula to determine the values of $R(P_n,K_{1,m})$, where $P_n$ is a path on $n$ vertices and $K_{1,m}$ is a star on $m+1$ vertices. In this note, we study the Ramsey numbers $R(P_n,K_1\vee F_m)$, where $F_m$ is a linear forest on $m$ vertices. We determine the exact values of $R(P_n,K_1\vee F_m)$ for the cases $m\le n$ and $m\ge 2n$, and for the case that $F_m$ has no odd component. Moreover, we...

A nonincreasing sequence $\pi =(d_1,...,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. In this case, $G$ is referred to as a realization of $\pi$. Given two graphs $G_1$ and $G_2$, A. Busch et al. (2014) introduced the potential-Ramsey number of $G_1$ and $G_2$, denoted by $r_{\mathrm{pot}}(G_1,G_2)$, as the smallest nonnegative integer $m$ such that for every $m$-term graphic sequence $\pi$, there is a realization $G$ of $\pi$ with $G_1\subseteq G$ or with $G_2\subseteq \overline{G}$, where $\overline{G}$ is the complement of $G$. For $t\ge 2$ and $0\le k\le \lfloor \frac{t}{2}\rfloor$, let $K_t^{-k}$ be the graph...