For any two positive integers $n$ and $k\ge 2$, let $G(n,k)$ be a digraph whose set of vertices is $\{0,1,...,n-1\}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^k\equiv b(modn)$. Let $n={\prod }_{i=1}^r{p}_i^{e_i}$ be the prime factorization of $n$. Let $P$ be the set of all primes dividing $n$ and let $P_1,P_2\subseteq P$ be such that $P_1\cup P_2=P$ and $P_1\cap P_2=\varnothing$. A fundamental constituent of $G(n,k)$, denoted by $G_{P_2}^{*}(n,k)$, is a subdigraph of $G(n,k)$ induced on the set of vertices which are multiples of ${\prod }_{p_i\in P_2}{p}_i$ and are relatively prime to all primes $q\in P_1$. L. Somer and M. Křížek proved that the trees attached...

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.

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

We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let $D=(V,A)$ be a reflexive digraph (or network). Consider $X$ and $Y$ (not necessarily disjoint) nonempty subsets of vertices (or nodes) of $D$. A disimplex $K(X,Y)$ of $D$ 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 majority coloring of a digraph $D$ with $k$ colors is an assignment $\pi :V\left(D\right)\to \{1,2,\cdots ,k\}$ such that for every $v\in V\left(D\right)$ we have $\pi \left(w\right)=\pi \left(v\right)$ for at most half of all out-neighbors $w\in N^{+}\left(v\right)$. A digraph $D$ is majority $k$-choosable if for any assignment of lists of colors of size $k$ to the vertices, there is a majority coloring of $D$ from these lists. We prove that if $U\left(D\right)$ is a 1-planar graph without a 4-cycle, then $D$ is majority 3-choosable. And we also prove that every NIC-planar digraph is majority 3-choosable.

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $\lceil n/d\rceil$. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that ${\alpha }_0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least ${\alpha }_{0}n$ contains a directed triangle. Let $ϵ<(3-2{\alpha }_0)/(4-2{\alpha }_0)$ be a positive real. We show that if $D$ is an oriented graph...

A directed Cayley graph $C(\Gamma ,X)$ is specified by a group $\Gamma$ and an identity-free generating set $X$ for this group. Vertices of $C(\Gamma ,X)$ are elements of $\Gamma$ and there is a directed edge from the vertex $u$ to the vertex $v$ in $C(\Gamma ,X)$ if and only if there is a generator $x\in X$ such that $ux=v$. We study graphs $C(\Gamma ,X)$ for the direct product $Z_m\times Z_n$ of two cyclic groups $Z_m$ and $Z_n$, and the generating set $X=\left\{\right(0,1),(1,0),(2,0),\cdots ,(p,0\left)\right\}$. We present resolving sets which yield upper bounds on the metric dimension of these graphs for $p=2$ and $3$.

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

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

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.

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

The Turán number of a given graph $H$, denoted by $\mathrm{ex}(n,H)$, is the maximum number of edges in an $H$-free graph on $n$ vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number $\text{ex}(n,K_p\cup K_q$) of a vertex-disjoint union of cliques $K_p$ and $K_q$ for all values of $n$.

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