Graphs satisfying inequality \(\theta(G^2) \leq \theta(G)\) (Q1613456)

An edge clique cover of a graph \(G\) is a collection of cliques that include all edges of \(G\). Denote by \(\theta(G)\) the smallest number of cliques that form an edge clique cover of \(G\). The authors study the relationship between \(\theta (G)\) and \(\theta(G^2)\), where \(G^2\) denotes the square of \(G\), i.e. the graph obtained from \(G\) by adding edges joining vertices \(u\) and \(v\) whenever the distance between \(u\) and \(v\) in \(G\) is 2. The main results of the paper are: If \(G\) is a connected graph with \(n\) vertices and \(\theta (G)\geq n\), then \(\theta(G^2)\leq \theta(G)\). If \(G\) is a connected chordal graph with \(n\) vertices such that \(\theta(G)\) is equal to \(n-1\) or \(n-2\), then \(\theta(G^2)\leq\theta(G)\). If \(T\) is a tree with \(n\) vertices, \(n\geq 3\), and \(m\) is the number of leaves in \(T\), then \(\theta(T^2)=n-m\).