An open triangle is a 3-vertex subgraph with two edges, i.e., an induced path of length 2. A formula for the maximum number of open triangles in n-vertex graphs with n edges is proved in the paper. We also present a full characterization of graphsfor which the maximum is attained.
Предметные области OECD FOS+WOS
- 1.01 МАТЕМАТИКА