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 $R$ be a commutative ring. The annihilator graph of $R$, denoted by $\mathrm{AG}\left(R\right)$, is the undirected graph with all nonzero zero-divisors of $R$ as vertex set, and two distinct vertices $x$ and $y$ are adjacent if and only if ${\mathrm{ann}}_R\left(xy\right)\ne {\mathrm{ann}}_R\left(x\right)\cup {\mathrm{ann}}_R\left(y\right)$, where for $z\in R$, ${\mathrm{ann}}_R\left(z\right)=\{r\in R:rz=0\}$. In this paper, we characterize all finite commutative rings $R$ with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings $R$ whose annihilator graphs have clique number $1$, $2$ or $3$. Also, we investigate some properties...

Let X be a Polish space, and let C₀ and C₁ be disjoint coanalytic subsets of X. The pair (C₀,C₁) is said to be complete if for every pair (D₀,D₁) of disjoint coanalytic subsets of ${\omega }^{\omega }$ there exists a continuous function $f:{\omega }^{\omega }\to X$ such that $f^{-1}\left(C₀\right)=D₀$ and $f^{-1}\left(C₁\right)=D₁$. We give several explicit examples of complete pairs of coanalytic sets.

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

A graph $X$, with a group $G$ of automorphisms of $X$, is said to be $(G,s)$-transitive, for some $s\ge 1$, if $G$ is transitive on $s$-arcs but not on $(s+1)$-arcs. Let $X$ be a connected $(G,s)$-transitive graph of prime valency $p\ge 5$, and $G_v$ the vertex stabilizer of a vertex $v\in V\left(X\right)$. Suppose that $G_v$ is solvable. Weiss (1974) proved that $|G_v{|\mid p(p-1)}^2$. In this paper, we prove that $G_v\cong ({\mathbb{Z}}_p⋊{\mathbb{Z}}_m)\times {\mathbb{Z}}_n$ for some positive integers $m$ and $n$ such that $ndivm$ and $m\mid p-1$.

In this paper, we introduce a new kind of rings that behave like semicommutative rings, but satisfy yet more known results. This kind of rings is called $P$-semicommutative. We prove that a ring $R$ is $P$-semicommutative if and only if $R\left[x\right]$ is $P$-semicommutative if and only if $R[x,x^{-1}]$ is $P$-semicommutative. Also, if $R\left[\right[x\left]\right]$ is $P$-semicommutative, then $R$ is $P$-semicommutative. The converse holds provided that $P\left(R\right)$ is nilpotent and $R$ is power serieswise Armendariz. For each positive integer $n$, $R$ is $P$-semicommutative...

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

In this paper, we study the size of the giant component $C_G$ in the random geometric graph $G=G(n,r_n,f)$ of $n$ nodes independently distributed each according to a certain density $f(·)$ in ${[0,1]}^2$ satisfying ${inf}_{x\in {[0,1]}^2}f\left(x\right)gt;$ $0$. If $\frac{c_1}{n}\le r_n^2\le c_2\frac{logn}{n}$ for some positive constants $c_1$, $c_2$ and $n{r}_n^2⟶\infty$ as $n\to \infty$, we show that the giant component of $G$ contains at least $n-\mathrm{o}\left(n\right)$ nodes with probability at least $1-{\mathrm{e}}^{-\beta n{r}_n^2}$ for all $n$ and for some positive constant $\beta$. We also obtain estimates on the diameter and number of the non-giant components of $G$.

Let $T_1,\cdots ,T_d$ be homogeneous trees with degrees $q_1+1,\cdots ,q_d+1\ge 3$, respectively. For each tree, let $𝔥:T_j\to \mathbb{Z}$ be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of $T_1,\cdots ,T_d$ is the graph $\mathrm{𝖣𝖫}(q_1,\cdots ,q_d)$ consisting of all $d$-tuples $x_1\cdots x_d\in T_1\times \cdots \times T_d$ with $𝔥\left(x_1\right)+\cdots +𝔥\left(x_d\right)=0$, equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If $d=2$ and $q_1=q_2=q$ then we obtain a Cayley 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 $C$ be a hyperelliptic curve of genus $g\ge 1$ over a number field $K$ with good reduction outside a finite set of places $S$ of $K$. We prove that $C$ has a Weierstrass model over the ring of integers of $K$ with height effectively bounded only in terms of $g$, $S$ and $K$. In particular, we obtain that for any given number field $K$, finite set of places $S$ of $K$ and integer $g\ge 1$ one can in principle determine the set of $K$-isomorphism classes of hyperelliptic curves over $K$ of genus $g$ with good reduction outside...

Let ${\mu }_{n-1}\left(G\right)$ be the algebraic connectivity, and let ${\mu }_1\left(G\right)$ be the Laplacian spectral radius of a $k$-connected graph $G$ with $n$ vertices and $m$ edges. In this paper, we prove that $${\mu }_{n-1}\left(G\right)\ge \frac{2n{k}^2}{(n(n-1)-2m)(n+k-2)+2k^2},$$ with equality if and only if $G$ is the complete graph $K_n$ or $K_n-e$. Moreover, if $G$ is non-regular, then $${\mu }_1\left(G\right)<2\Delta -\frac{2(n\Delta -2m)k^2}{2(n\Delta -2m)(n^2-2n+2k)+n{k}^2},$$ where $\Delta$ stands for the maximum degree of $G$. Remark that in some cases, these two inequalities improve some previously known results.

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is $val\left(f\right)={\Sigma }_{e\in E\left(G\right)}{f}^{\text{'}}K\left(e\right)$. The maximum value of a γ-labeling of G is defined as $va{l}_{max}\left(G\right)=maxval\left(f\right):fisa\gamma -labelingofG$; while the minimum value of a γ-labeling of G is $va{l}_{min}\left(G\right)=minval\left(f\right):fisa\gamma -labelingofG$; The values $va{l}_{max}\left(S_{p,q}\right)$ and $va{l}_{min}\left(S_{p,q}\right)$ are determined for double stars $S_{p,q}$. We present characterizations of connected graphs G of order n for which...

Let $R$ be a commutative ring with unity and $U\left(R\right)$ be the set of unit elements of $R$. In this paper, we introduce and investigate some properties of a new kind of graph on the ring $R$, namely, the prime ideals intersection graph of $R$, denoted by $G_p\left(R\right)$. The $G_p\left(R\right)$ is a graph with vertex set $R^{*}-U\left(R\right)$ and two distinct vertices $a$ and $b$ are adjacent if and only if there exists a prime ideal $𝔭$ of $R$ such that $a,b\in 𝔭$. We obtain necessary and sufficient conditions on $R$ such that $G_p\left(R\right)$ is disconnected. We find the diameter and...

Let ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ be the following algorithmic problem: Given a finite simplicial complex $K$ of dimension at most $k$, does there exist a (piecewise linear) embedding of $K$ into ${ℝ}^d$? Known results easily imply polynomiality of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2}$ ($k=1,2$; the case $k=1,d=2$ is graph planarity) and of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2k}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{d\to d}$ and ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{(d-1)\to d}$ are undecidable for each ${}_d\ge 5$. Our main result is NP-hardness of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{2\to 4}$ and, more generally, of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ for all...

This paper classifies surfaces $S$ of general type with $p_g=q=1$ having an involution $i$ such that $S/i$ has non-negative Kodaira dimension and that the bicanonical map of $S$ factors through the double cover induced by $i.$ It is shown that $S/i$ is regular and either: a) the Albanese fibration of $S$ is of genus 2 or b) $S$ has no genus 2 fibration and $S/i$ is birational to a $K3$ surface. For case a) a list of possibilities and examples are given. An example for case b) with $K^2=6$ is also constructed.