scientific article; zbMATH DE number 3970790

From MaRDI portal
Publication:3737459





An ordinary graph is a finite linear graph which contains no loops or multiple edges, and in which all edges are undirected. In such a graph G, let e(G) and t(G) denote respectively the number of edges and triangles. Let \(n\geq r\geq 1\) and \(n=rk+\nu\), where n, r, k, \(\nu\) are integers and \(0\leq \nu \leq r-1\). Further let \(T_ r(n)\) denote a graph with n vertices and the following structure: the vertices are partitioned into \(\nu\) classes of \(k+1\) and r-\(\nu\) classes of k elements each, the classes being mutually disjoint, and two vertices are joined by an edge if and only if they do not belong to the same class. The main result in this paper is the following Theorem. Let n and r be integers, \(n\geq r\geq 2\), and G be an ordinary graph with n vertices. If \(t(G)\leq t(T_ r(n))\), then \(e(G)\leq e(T_ r(n))\) and equality \(e(G)=e(T_ r(n))\) holds if and only if the graph G is isomorphic to \(T_ r(n)\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3737459)