The paper gives an account of previous and recent attempts to determine the order of a smallest graph not containing K₅ and such that every 2-coloring of its edges results in a monochromatic triangle. A new 14-vertex K₄-free graph with the same Ramsey property in the vertex coloring case is found. This yields a new construction of one of the only two known 15-vertex (3,3)-Ramsey graphs not containing K₅.

An R-tree is a geodesic space for which there is a unique arc joining any two of its points, and this arc is a metric segment. If X is a closed convex subset of an R-tree Y, and if T: X → 2Y is a multivalued mapping, then a point z for which [...] is called a point of best approximation. It is shown here that if T is an ε-semicontinuous mapping whose values are nonempty closed convex subsets of Y, and if T has at least two distinct points of best approximation, then T must have a fixed point. We...

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

Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority...

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.

This paper consists of two parts. The first part is devoted to the study of continuous diagrams and their connections with the boolean convolution. In the second part we investigate the rectangular Young diagrams and respective discrete measures. We recall the definition of Kerov's α-transformation of diagrams, define the α-transformation of finitely supported discrete measures and generalize the notion of the α-transformation.

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.