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)$.

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$...

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...

Let $G$ be a finite group and construct a graph $\Delta \left(G\right)$ by taking $G\setminus \left\{1\right\}$ as the vertex set of $\Delta \left(G\right)$ and by drawing an edge between two vertices $x$ and $y$ if $\langle x,y\rangle$ is cyclic. Let $K\left(G\right)$ be the set consisting of the universal vertices of $\Delta \left(G\right)$ along the identity element. For a solvable group $G$, we present a necessary and sufficient condition for $K\left(G\right)$ to be nontrivial. We also develop a connection between $\Delta \left(G\right)$ and $K\left(G\right)$ when $\left|G\right|$ is divisible by two distinct primes and the diameter of $\Delta \left(G\right)$ is 2.

Let $G$ be a simple graph, let $d\left(v\right)$ denote the degree of a vertex $v$ and let $g$ be a nonnegative integer function on $V\left(G\right)$ with $0\le g\left(v\right)\le d\left(v\right)$ for each vertex $v\in V\left(G\right)$. A $g_c$-coloring of $G$ is an edge coloring such that for each vertex $v\in V\left(G\right)$ and each color $c$, there are at least $g\left(v\right)$ edges colored $c$ incident with $v$. The $g_c$-chromatic index of $G$, denoted by ${\chi }_{g_c}^{\text{'}}\left(G\right)$, is the maximum number of colors such that a $g_c$-coloring of $G$ exists. Any simple graph $G$ has the $g_c$-chromatic index equal to ${\delta }_g\left(G\right)$ or ${\delta }_g\left(G\right)-1$, where ${\delta }_g\left(G\right)={min}_{v\in V\left(G\right)}\lfloor d\left(v\right)/g\left(v\right)\rfloor$. A graph $G$ is nearly bipartite,...

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$.

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)$....

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...

The Ramsey number $R(G,H)$ for a pair of graphs $G$ and $H$ is defined as the smallest integer $n$ such that, for any graph $F$ on $n$ vertices, either $F$ contains $G$ or $\overline{F}$ contains $H$ as a subgraph, where $\overline{F}$ denotes the complement of $F$. We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers $R(K_1+L_n,P_m)$ and $R(K_1+L_n,C_m)$ for some integers $m$, $n$, where $L_n$ is...

For a graph $G=(V,E)$, a double Roman dominating function is a function $f:V\to \{0,1,2,3\}$ having the property that if $f\left(v\right)=0$, then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f\left(w\right)=3$, and if $f\left(v\right)=1$, then the vertex $v$ must have at least one neighbor with $f\left(w\right)\ge 2$. The weight of a double Roman dominating function $f$ is the sum $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by ${\gamma }_{\mathrm{dR}}\left(G\right)$. In this paper, we establish a new...

For a fixed positive integer $k$ and $G=(V,E)$ a connected graph of order $n$, whose minimum vertex degree is at least $k$, a set $S\subseteq V$ is a total $k$-dominating set, also known as a $k$-tuple total dominating set, if every vertex $v\in V$ has at least $k$ neighbors in $S$. The minimum size of a total $k$-dominating set for $G$ is called the total $k$-domination number of $G$, denoted by ${\gamma }_{kt}\left(G\right)$. The total $k$-domination problem is to determine a minimum total $k$-dominating set of $G$. Since the exact problem is in general quite difficult...

Let $T$ be a tree with $n$ vertices. To each edge of $T$ we assign a weight which is a positive definite matrix of some fixed order, say, $s$. Let $D_{ij}$ denote the sum of all the weights lying in the path connecting the vertices $i$ and $j$ of $T$. We now say that $D_{ij}$ is the distance between $i$ and $j$. Define $D:=\left[D_{ij}\right]$, where $D_{ii}$ is the $s\times s$ null matrix and for $i\ne j$, $D_{ij}$ is the distance between $i$ and $j$. Let $G$ be an arbitrary connected weighted graph with $n$ vertices, where each weight is a positive definite matrix of order...

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...

Given a graph $G=(V,E)$, if we can partition the vertex set $V$ into two nonempty subsets $V_1$ and $V_2$ which satisfy $\Delta \left(G\left[V_1\right]\right)\le d_1$ and $\Delta \left(G\left[V_2\right]\right)\le d_2$, then we say $G$ has a $({\Delta }_{d_1},{\Delta }_{d_2})$-partition. And we say $G$ admits an $(F_{d_1},F_{d_2})$-partition if $G\left[V_1\right]$ and $G\left[V_2\right]$ are both forests whose maximum degree is at most $d_1$ and $d_2$, respectively. We show that every planar graph with girth at least 5 has an $(F_4,F_4)$-partition.

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. ...