×

On three conjectures of GRAFFITI. (English) Zbl 0897.05034

Three conjectures of the computer program GRAFFITI are considered. The conjecture asserting that if \(G\) is a connected graph then \(\text{rad} (G)\leq \mu (G)+R(G)\) is disproved, where \(\text{rad} (G)\), \(\mu (G)\) and \(R(G)\) are the radius, the average distance and the sum of the inverse degrees of the vertices in \(G\), respectively. If \(G\) is a connected graph of order \(p\) and \(v\) is a vertex of \(G\), then \(E(v)\) denote the number of vertices at an even distance from \(v\) and \(\text{Even} (G)\) denote a vector whose components are \(E(v)\) for \(v\in V(G)\). The mean of \(\text{Even} (G)\) is denoted by \(\text{ME} (G)\). The authors prove a conjecture proposed by J. B. Shearer [Discrete Math. 46, 83-87 (1983; Zbl 0516.05053)] asserting that there exist connected triangle-free graphs \(G\) of order \(p\) for which \(\text{ME} (G)=o(p)\). Moreover, it is proved that every connected graph with minimum degree \(\delta \) and diameter \(d\) contains a matching of size at least \(\delta (d+1)/6\). This inequality improves one of the conjectures under the additional assumption that \(\delta \geq 6\).

MSC:

05C12 Distance in graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0516.05053

Software:

GRAFFITI
PDFBibTeX XMLCite