Let $T$ be a tree. Then a vertex of $T$ with degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$. The set of leaves of $T$ is denoted by $L\left(T\right)$ and the set of branch vertices of $T$ is denoted by $B\left(T\right)$. For two distinct vertices $u$, $v$ of $T$, let $P_T[u,v]$ denote the unique path in $T$ connecting $u$ and $v.$ Let $T$ be a tree with $B\left(T\right)\ne \varnothing$. For each leaf $x$ of $T$, let $y_x$ denote the nearest branch vertex to $x$. We delete $V\left(P_T[x,y_x]\right)\setminus \left\{y_x\right\}$ from $T$ for all $x\in L\left(T\right)$. The resulting subtree of $T$ is called the reducible stem...

For a digraph $D$, the niche hypergraph $N\mathscr{H}\left(D\right)$ of $D$ is the hypergraph having the same set of vertices as $D$ and the set of hyperedges $E\left(N\mathscr{H}\right(D\left)\right)=\{e\subseteq V(D):|e|\ge 2$ and there exists a vertex $v$ such that $e=N_D^{-}\left(v\right)$ or $e=N_D^{+}\left(v\right)\}$. A digraph is said to be acyclic if it has no directed cycle as a subdigraph. For a given hypergraph $\mathscr{H}$, the niche number $\widehat{n}\left(\mathscr{H}\right)$ is the smallest integer such that $\mathscr{H}$ together with $\widehat{n}\left(\mathscr{H}\right)$ isolated vertices is the niche hypergraph of an acyclic digraph. C. Garske, M. Sonntag and H. M. Teichert (2016) conjectured that for a linear...

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

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

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

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

A proper coloring $c:V\left(G\right)\to \{1,2,...,k\}$, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c^{\text{'}}:E\left(G\right)\to \{1,2,...,k-1\}$ defined by $c^{\text{'}}\left(uv\right)=|c\left(u\right)-c\left(v\right)|$ for each edge $uv$ of $G$ is also proper. The minimum integer $k$ for which $G$ has a graceful $k$-coloring is the graceful chromatic number ${\chi }_g\left(G\right)$. It is known that if $T$ is a tree with maximum degree $\Delta$, then ${\chi }_g\left(T\right)\le \lceil \frac{5}{3}\Delta \rceil$ and this bound is best possible. It is shown for each integer $\Delta \ge 2$ that there is an infinite class of trees $T$ with maximum degree $\Delta$ such that ${\chi }_g\left(T\right)=\lceil \frac{5}{3}\Delta \rceil$. In particular, we investigate for each...

Let $G$ be a finite group and let $\pi \left(G\right)=\{p_1,p_2,...,p_k\}$ be the set of prime divisors of $\left|G\right|$ for which $p_1<p_2<\cdots <p_k$. The Gruenberg-Kegel graph of $G$, denoted $GK\left(G\right)$, is defined as follows: its vertex set is $\pi \left(G\right)$ and two different vertices $p_i$ and $p_j$ are adjacent by an edge if and only if $G$ contains an element of order $p_i{p}_j$. The degree of a vertex $p_i$ in $\mathrm{GK}\left(G\right)$ is denoted by $d_G\left(p_i\right)$ and the $k$-tuple $D\left(G\right)=(d_G\left(p_1\right),d_G\left(p_2\right),...,d_G\left(p_k\right))$ is said to be the degree pattern of $G$. Moreover, if $\omega \subseteq \pi \left(G\right)$ is the vertex set of a connected component of $GK\left(G\right)$, then the largest $\omega$-number which divides $\left|G\right|$, is...

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

A graph $G$ is a $k$-tree if either $G$ is the complete graph on $k+1$ vertices, or $G$ has a vertex $v$ whose neighborhood is a clique of order $k$ and the graph obtained by removing $v$ from $G$ is also a $k$-tree. Clearly, a $k$-tree has at least $k+1$ vertices, and $G$ is a 1-tree (usual tree) if and only if it is a $1$-connected graph and has no $K_3$-minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of $k$-trees as follows: if $G$ is a graph with at least $k+1$ vertices, then $G$ is...