Let $\varphi$ be a substitution of Pisot type on the alphabet $𝒜=\{1,2,...,d\}$; $\varphi$ satisfies theif for every $i,j\in 𝒜$, there are integers $k,n$ such that ${\varphi }^n\left(i\right)$ and ${\varphi }^n\left(j\right)$ have the same $k$-th letter, and the prefixes of length $k-1$ of ${\varphi }^n\left(i\right)$ and ${\varphi }^n\left(j\right)$ have the same image under the abelianization map. We prove that the strong coincidence condition is satisfied if $d=2$ and provide a partial result for $d\ge 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,...

We prove that, assuming , if $X$ is a space with ${\aleph }_1$-calibre and a zeroset diagonal, then $X$ is submetrizable. This gives a consistent positive answer to the question of Buzyakova in Observations on spaces with zeroset or regular $G_{\delta }$-diagonals, Comment. Math. Univ. Carolin. 46 (2005), no. 3, 469–473. We also make some observations on spaces with ${\aleph }_1$-calibre.

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

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

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

A graph $G=(V,E)$ is called improperly $(d_1,\cdots ,d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1,\cdots ,V_k$ such that the graph $G\left[V_i\right]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1\le i\le k$. In this paper, we mainly study the improper coloring of $1$-planar graphs and show that $1$-planar graphs with girth at least $7$ are $(2,0,0,0)$-colorable.