Concordance graphs (Q1568783): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Peter C. Fishburn / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Normal rank |
Revision as of 05:59, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Concordance graphs |
scientific article |
Statements
Concordance graphs (English)
0 references
28 August 2000
0 references
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.
0 references
concordance graph
0 references
comparability graph
0 references
characterizations
0 references