Concordance graphs
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.
- Relation between the Kendall and Spearman coefficients and concordance graphs
- Simple congruence lattices of finite graphs
- On consistent families of circuits
- Sur les graphes admettant le nombre maximum de sous-graphes à trois sommets et deux arêtes, et les paires d'ordres totaux qui maximisent \(| Rho\)- Tau\(|\). (On the graphs which admit the maximal number of subgraphs on three vertices and with two edges
- scientific article; zbMATH DE number 4095519
This page was built for publication: Concordance graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1568783)
