Dankelmann, Peter; Swart, Henda C.; Oellermann, Ortrud R. On three conjectures of GRAFFITI. (English) Zbl 0897.05034 J. Comb. Math. Comb. Comput. 26, 131-137 (1998). 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\). Reviewer: I.Tomescu (Bucureşti) Cited in 2 Documents MSC: 05C12 Distance in graphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:average distance; triangle-free graph; diameter; matching number Citations:Zbl 0516.05053 Software:GRAFFITI PDFBibTeX XMLCite \textit{P. Dankelmann} et al., J. Comb. Math. Comb. Comput. 26, 131--137 (1998; Zbl 0897.05034)