Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_G\left(x\right)\subseteq N_G\left[u\right]\cup N_G\left[v\right]$, where $N_G\left[x\right]=N_G\left(x\right)\cup x$. In the case where G is a claw-free graph, G* is equal to G². We define $\sigma °ₜ=min{\sum }_{x\in S}{d}_G\left(x\right):SisanindependentsetinG*and\left|S\right|=t$. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

The restrained domination number ${\gamma }^r\left(G\right)$ and the total restrained domination number ${\gamma }_t^r\left(G\right)$ of a graph $G$ were introduced recently by various authors as certain variants of the domination number $\gamma \left(G\right)$ of $\left(G\right)$. A well-known numerical invariant of a graph is the domatic number $d\left(G\right)$ which is in a certain way related (and may be called dual) to $\gamma \left(G\right)$. The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.

Let $G$ be a graph with $n$ vertices, $m$ edges and a vertex degree sequence $(d_1,d_2,\cdots ,d_n)$, where $d_1\ge d_2\ge \cdots \ge d_n$. The spectral radius and the largest Laplacian eigenvalue are denoted by $\rho \left(G\right)$ and $\mu \left(G\right)$, respectively. We determine the graphs with $$\rho \left(G\right)=\frac{d_n-1}{2}+\sqrt{2m-n{d}_n+\frac{{(d_n+1)}^2}{4}}$$ and the graphs with $d_n\ge 1$ and $$\mu \left(G\right)=d_n+\frac{1}{2}+\sqrt{{\sum }_{i=1}^n{d}_i(d_i-d_n)+{\left(d_n-\frac{1}{2}\right)}^2}.$$ We also present some sharp lower bounds for the Laplacian eigenvalues of a connected graph.

In this paper we compute some bounds of the Balaban index and then by means of group action we compute the Balaban index of vertex transitive graphs. ACM Computing Classification System (1998): G.2.2 , F.2.2.

We give a novel upper bound on graph energy in terms of the vertex cover number, and present a complete characterization of the graphs whose energy equals twice their matching number.

We consider the problem of the existence of uniquely partitionable planar graphs. We survey some recent results and we prove the nonexistence of uniquely (𝓓₁,𝓓₁)-partitionable planar graphs with respect to the property 𝓓₁ "to be a forest".

Guoliang Yu has introduced a property on discrete metric spaces and groups, which is a weak form of amenability and which has important applications to the Novikov conjecture and the coarse Baum–Connes conjecture. The aim of the present paper is to prove that property in particular examples, like spaces with subexponential growth, amalgamated free products of discrete groups having property A and HNN extensions of discrete groups having property A.

The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.

The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.

The paper studies tolerances and congruences on anticommutative conservative groupoids. These groupoids can be assigned in a one-to-one way to undirected graphs.