In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g(n,l)$, the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$. By edit distance of two graphs $G$, $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$. This new extremal number $g(n,l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

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.

For a graph $G=(V,E)$, a double Roman dominating function is a function $f:V\to \{0,1,2,3\}$ having the property that if $f\left(v\right)=0$, then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f\left(w\right)=3$, and if $f\left(v\right)=1$, then the vertex $v$ must have at least one neighbor with $f\left(w\right)\ge 2$. The weight of a double Roman dominating function $f$ is the sum $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by ${\gamma }_{\mathrm{dR}}\left(G\right)$. In this paper, we establish a new...

For any collection of graphs $G₁,...,G_N$ we find the minimal dimension d such that the product $G₁\times ...\times G_N$ is embeddable into ${ℝ}^d$ (see Theorem 1 below). In particular, we prove that (K₅)ⁿ and $\left(K_{3,3}\right)ⁿ$ are not embeddable into ${ℝ}^{2n}$, where K₅ and $K_{3,3}$ are the Kuratowski graphs. This is a solution of a problem of Menger from 1929. The idea of the proof is a reduction to a problem from so-called Ramsey link theory: we show that any embedding $LkO\to S^{2n-1}$, where O is a vertex of (K₅)ⁿ, has a pair of linked (n-1)-spheres.

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

Given a graph $G$, let $f\left(G\right)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f\left(G\right)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,{\theta }_{k,s})\ge \frac{1}{2}m+\Omega \left(m^{(2k+1)/(2k+2)}\right)$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K_k^{\text{'}}$ and $K_{t,s}^{\text{'}}$ for the subdivisions of $K_k$ and $K_{t,s}$. We show that $f(m,K_k^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5k-8)/(6k-10)}\right)$ and $f(m,K_{t,s}^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5t-1)/(6t-2)}\right)$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on...

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

Suppose that $A$ is a real symmetric matrix of order $n$. Denote by $m_A\left(0\right)$ the nullity of $A$. For a nonempty subset $\alpha$ of $\{1,2,...,n\}$, let $A\left(\alpha \right)$ be the principal submatrix of $A$ obtained from $A$ by deleting the rows and columns indexed by $\alpha$. When $m_{A\left(\alpha \right)}\left(0\right)=m_A\left(0\right)+\left|\alpha \right|$, we call $\alpha$ a P-set of $A$. It is known that every P-set of $A$ contains at most $\lfloor n/2\rfloor$ elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As...

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

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

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