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

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

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

A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle in $G$. In other words, each cycle of $G$ must be colored with at least three colors. Given a list assignment $L=\left\{L\right(v):v\in V\}$, if there exists an acyclic coloring $\pi$ of $G$ such that $\pi \left(v\right)\in L\left(v\right)$ for all $v\in V$, then we say that $G$ is acyclically $L$-colorable. If $G$ is acyclically $L$-colorable for any list assignment $L$ with $\left|L\right(v\left)\right|\ge k$ for all $v\in V$, then $G$ is acyclically $k$-choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without...

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

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

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

For graphs $G$, $F_1$, $F_2$, we write $G\to (F_1,F_2)$ if for every red-blue colouring of the edge set of $G$ we have a red copy of $F_1$ or a blue copy of $F_2$ in $G$. The size Ramsey number $\widehat{r}(F_1,F_2)$ is the minimum number of edges of a graph $G$ such that $G\to (F_1,F_2)$. Erdős and Faudree proved that for the cycle $C_n$ of length $n$ and for $t\ge 2$ matchings $t{K}_2$, the size Ramsey number $\widehat{r}(t{K}_2,C_n)<n+(4t+3)\sqrt{n}$. We improve their upper bound for $t=2$ and $t=3$ by showing that $\widehat{r}(2K_2,C_n)\le n+2\sqrt{3n}+9$ for $n\ge 12$ and $\widehat{r}(3K_2,C_n)<n+6\sqrt{n}+9$ for $n\ge 25$.