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

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 graph is called distance integral (or $D$-integral) if all eigenvalues of its distance matrix are integers. In their study of $D$-integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$-integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_1,p_2,p_3}$ with $p_1<p_2<p_3$, and $K_{p_1,p_2,p_3,p_4}$ with $p_1<p_2<p_3<p_4$, as well as the infinite classes of distance integral...

For a simple graph $G$ on $n$ vertices and an integer $k$ with $1\le k\le n$, denote by ${𝒮}_k^{+}\left(G\right)$ the sum of $k$ largest signless Laplacian eigenvalues of $G$. It was conjectured that ${𝒮}_k^{+}\left(G\right)\le e\left(G\right)+\left(\genfrac{}{}{0pt}{}{k+1}{2}\right)$, where $e\left(G\right)$ is the number of edges of $G$. This conjecture has been proved to be true for all graphs when $k\in \{1,2,n-1,n\}$, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all $k$). In this note, this conjecture is proved to be true for all graphs when $k=n-2$, and for some new classes of graphs.

We show that, given any n and α, any embedding of any sufficiently large complete graph in ℝ³ contains an oriented link with components Q₁, ..., Qₙ such that for every i ≠ j, $\left|lk\right(Q_i,Q_j\left)\right|\ge \alpha$ and $\left|a₂\right(Q_i\left)\right|\ge \alpha$, where $a₂\left(Q_i\right)$ denotes the second coefficient of the Conway polynomial of $Q_i$.

We study the generalized $k$-connectivity ${\kappa }_k\left(G\right)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$-edge-connectivity ${\lambda }_k\left(G\right)$. We determine the exact value of ${\kappa }_k\left(G\right)$ and ${\lambda }_k\left(G\right)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k=3$.

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number ${\chi }_D\left(G\right)$ of G. Extending these concepts to infinite graphs we prove that $D\left(Q_{\aleph }₀\right)=2$ and ${\chi }_D\left(Q_{\aleph }₀\right)=3$, where $Q_{\aleph }₀$ denotes the hypercube of countable dimension. We also show that ${\chi }_D\left(Q₄\right)=4$, thereby completing the investigation of finite hypercubes with respect to ${\chi }_D$. Our...

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.

The generalized non-commutative torus $T_{\varrho }^k$ of rank n is defined by the crossed product $A_{m/k}{\times }_{\alpha ₃}\mathbb{Z}{\times }_{\alpha ₄}...{\times }_{\alpha ₙ}\mathbb{Z}$, where the actions ${\alpha }_i$ of ℤ on the fibre $M_k\left(ℂ\right)$ of a rational rotation algebra $A_{m/k}$ are trivial, and $C*\left(k\mathbb{Z}\times k\mathbb{Z}\right){\times }_{\alpha ₃}\mathbb{Z}{\times }_{\alpha ₄}...{\times }_{\alpha ₙ}\mathbb{Z}$ is a non-commutative torus $A_{\varrho }$. It is shown that $T_{\varrho }^k$ is strongly Morita equivalent to $A_{\varrho }$, and that $T_{\varrho }^k\otimes M_{p^{\infty }}$ is isomorphic to $A_{\varrho }\otimes M_k\left(ℂ\right)\otimes M_{p^{\infty }}$ if and only if the set of prime factors of k is a subset of the set of prime factors of p.

Let $\gamma \left(G\right)$ and $i\left(G\right)$ be the domination number and the independent domination number of $G$, respectively. Rad and Volkmann posted a conjecture that $i\left(G\right)/\gamma \left(G\right)\le \Delta \left(G\right)/2$ for any graph $G$, where $\Delta \left(G\right)$ is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than $\Delta \left(G\right)/2$ are provided as well.

Let $S$ be a fixed symmetric finite subset of $S{L}_d\left({𝒪}_K\right)$ that generates a Zariski dense subgroup of $S{L}_d\left({𝒪}_K\right)$ when we consider it as an algebraic group over $mathbbQ$ by restriction of scalars. We prove that the Cayley graphs of $S{L}_d({𝒪}_K/I)$ with respect to the projections of $S$ is an expander family if $I$ ranges over square-free ideals of ${𝒪}_K$ if $d=2$ and $K$ is an arbitrary numberfield, or if $d=3$ and $K=\mathbb{Q}$.

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{All}$, $E_{Some}$, $E_{None}$ of the edge set E, where: $E_{All}$ = e ∈ E, e belongs to all optimum solutions, $E_{None}$ = e ∈ E, e does not belong to any optimum solution and $E_{Some}$ = e ∈ E, e belongs to some but not to all optimum solutions.

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

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

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