Concordance graphs (Q1568783)

Let \(G= (V,E)\) be a finite simple graph with \(n\geq 2\) vertices. \(G\) is called a concordance graph if the number of its induced three-vertex one-edged subgraphs equals the number of its induced three-vertex two-edged subgraphs, the class of these graphs be denoted by \({\mathfrak C}\). If \(L\) and \(L'\) are linear orders defined on \(V\), then the graph \(G(L\cap L')\) of the partially ordered set \((V,L\cap L')\) is the graph with vertex set \(V\) and edge set \(\{\{u, v\}\in V\mid u(L\cap L')v\) or \(v(L\cap L')u\}\). It is called the comparability graph. A concordance graph is proper if it is the comparability graph of a partially ordered set of order dimension 1 or 2. Let \({\mathfrak P}= \{G\in{\mathfrak C}\mid G\) is proper\}. The authors get the following results: At first they establish two basic structural characterizations: (1) \(G\in{\mathfrak C}\) if and only if \((n+1) \sum d_v+ 12t= 3 \sum d^2_v\) (Theorem 2.1). (2) \(G\in{\mathfrak P}\) if and only if every odd cycle in \(G^{\text{c}}\) has a triangular chord (Theorem 2.2). Here \(d_v\) denote the degree of \(v\in V\) in \(G= (V,E)\) and \(G^{\text{c}}\) the complement of \(G\), \(t\) is the number of induced \(K_3\) in \(G\) and \(n=|V|\). These results are commented in detail and the improper concordance graphs for \(n= 7\) and all proper concordance graphs with \(2\leq n\leq 7\) and \(0<|E|<{1\over 2}\left(\begin{smallmatrix} n\\ 2\end{smallmatrix}\right)\) are illustrated by figures. Then the authors are concerned with infinite families of \({\mathfrak C}\) and especially such a family in \({\mathfrak P}\) for each \(t\in \{0,1,\dots\}\) is described. Finally, an infinite family of regular concordance graphs is specified. If \({\mathfrak R}= \{G\in{\mathfrak C}\mid G\) is \(d\)-regular for some \(0< d< n-1\}\) and \({\mathfrak R}_d\) denotes the set of \(d\)-regular graphs in \({\mathfrak R}\), then the authors get that for every \(d\geq 2\), there is a \(G\in{\mathfrak R}_d\) with \(|V|= 3d-1\) (Theorem 5.2). Two open problems are formulated.