A construction of imprimitive symmetric graphs which are not multicovers of their quotients (Q409392): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
A sequence of \(s+1\) vertices of a finite, nonempty graph \(\Gamma\) is an \textit{s-arc} if any two consecutive terms are adjacent and any three consecutive terms are distinct. A finite group \(X\) acting on \(V(\Gamma)\) \textit{preserves the structure of \(\Gamma\)} if two vertices of \(\Gamma\) are adjacent iff their images under every element of \(X\) are adjacent. \(\Gamma\) is \textit{\((X,s)\)-arc-transitive} if, in addition, \(X\) is transitive on \(V(\Gamma)\) and on the set of \(s\)-arcs of \(\Gamma\). Then, a partition \(\mathcal B\) of \(V(\Gamma)\) is \textit{\(X\)-invariant} if \(\{\sigma^x|\sigma\in B\}\in \mathcal B\) for any \(B\in\mathcal B\) and any \(x\in X\). A finite \(X\)-symmetric graph \(\Gamma\) is \textit{imprimitive} if \(V(\Gamma)\) admits an \(X\)-invariant partition \(\mathcal B\) having some \(B\in\mathcal B\) with \(1<|B|<|V(\Gamma)|\); then the \textit{quotient graph} \(\Gamma_{\mathcal B}\) has vertex set \(\mathcal B\), in which two blocks are adjacent iff there exists at least one edge of \(\Gamma\) between them. Let \(\Sigma\) be a finite \(X\)-symmetric graph of valency \(\overline{b}\geq 2\). A \textit{star} is a set of \(\ell\)-arcs starting from the same vertex of \(\Sigma\), where \(\ell\geq1\). From the author's abstract: ``We give a sufficient and necessary condition for the existence of a class of finite, imprimitive \((X,s)\)-arc-transitive graphs which have a quotient isomorphic to \(\Sigma\) and are not multicovers of that quotient, together with a combinatorial method, called the \textit{double-star graph construction}, for constructing such graphs. Moreover, for any \(X\)-symmetric graph \(\Gamma\) admitting a nontrivial \(X\)-invariant partition \(\mathcal B\) such that \(\Gamma\) is not a multicover of \(\Gamma_{\mathcal B}\), we show that there exists a sequence of \(m+1\) \(X\)-invariant partitions \({\mathcal B}={\mathcal B}_0\), \({\mathcal B}_1\), \dots \({\mathcal B}_m\) of \(V(\Gamma)\), where \(m\geq1\) is an integer, such that \({\mathcal B}_i\) is a proper refinement of \({\mathcal B}_{i-1}\), and \(\Gamma_{{\mathcal B}_{i}}\) can be reconstructed from \(\Gamma_{{\mathcal B}_{i-1}}\) by the double-star graph construction for \(i=1,2,\dots m\), and that either \(\Gamma\cong\Gamma_{{\mathcal B}_m}\) or \(\Gamma\) is a multicover of \(\Gamma_{{\mathcal B}_m}\).'' | |||
Property / review text: A sequence of \(s+1\) vertices of a finite, nonempty graph \(\Gamma\) is an \textit{s-arc} if any two consecutive terms are adjacent and any three consecutive terms are distinct. A finite group \(X\) acting on \(V(\Gamma)\) \textit{preserves the structure of \(\Gamma\)} if two vertices of \(\Gamma\) are adjacent iff their images under every element of \(X\) are adjacent. \(\Gamma\) is \textit{\((X,s)\)-arc-transitive} if, in addition, \(X\) is transitive on \(V(\Gamma)\) and on the set of \(s\)-arcs of \(\Gamma\). Then, a partition \(\mathcal B\) of \(V(\Gamma)\) is \textit{\(X\)-invariant} if \(\{\sigma^x|\sigma\in B\}\in \mathcal B\) for any \(B\in\mathcal B\) and any \(x\in X\). A finite \(X\)-symmetric graph \(\Gamma\) is \textit{imprimitive} if \(V(\Gamma)\) admits an \(X\)-invariant partition \(\mathcal B\) having some \(B\in\mathcal B\) with \(1<|B|<|V(\Gamma)|\); then the \textit{quotient graph} \(\Gamma_{\mathcal B}\) has vertex set \(\mathcal B\), in which two blocks are adjacent iff there exists at least one edge of \(\Gamma\) between them. Let \(\Sigma\) be a finite \(X\)-symmetric graph of valency \(\overline{b}\geq 2\). A \textit{star} is a set of \(\ell\)-arcs starting from the same vertex of \(\Sigma\), where \(\ell\geq1\). From the author's abstract: ``We give a sufficient and necessary condition for the existence of a class of finite, imprimitive \((X,s)\)-arc-transitive graphs which have a quotient isomorphic to \(\Sigma\) and are not multicovers of that quotient, together with a combinatorial method, called the \textit{double-star graph construction}, for constructing such graphs. Moreover, for any \(X\)-symmetric graph \(\Gamma\) admitting a nontrivial \(X\)-invariant partition \(\mathcal B\) such that \(\Gamma\) is not a multicover of \(\Gamma_{\mathcal B}\), we show that there exists a sequence of \(m+1\) \(X\)-invariant partitions \({\mathcal B}={\mathcal B}_0\), \({\mathcal B}_1\), \dots \({\mathcal B}_m\) of \(V(\Gamma)\), where \(m\geq1\) is an integer, such that \({\mathcal B}_i\) is a proper refinement of \({\mathcal B}_{i-1}\), and \(\Gamma_{{\mathcal B}_{i}}\) can be reconstructed from \(\Gamma_{{\mathcal B}_{i-1}}\) by the double-star graph construction for \(i=1,2,\dots m\), and that either \(\Gamma\cong\Gamma_{{\mathcal B}_m}\) or \(\Gamma\) is a multicover of \(\Gamma_{{\mathcal B}_m}\).'' / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C70 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C60 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6023616 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
symmetric graph | |||
Property / zbMATH Keywords: symmetric graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
imprimitive graph | |||
Property / zbMATH Keywords: imprimitive graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multicover | |||
Property / zbMATH Keywords: multicover / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
quotient graph | |||
Property / zbMATH Keywords: quotient graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
double-star graph | |||
Property / zbMATH Keywords: double-star graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(s\)-arc-transitive graph | |||
Property / zbMATH Keywords: \(s\)-arc-transitive graph / rank | |||
Normal rank |
Revision as of 19:13, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A construction of imprimitive symmetric graphs which are not multicovers of their quotients |
scientific article |
Statements
A construction of imprimitive symmetric graphs which are not multicovers of their quotients (English)
0 references
13 April 2012
0 references
A sequence of \(s+1\) vertices of a finite, nonempty graph \(\Gamma\) is an \textit{s-arc} if any two consecutive terms are adjacent and any three consecutive terms are distinct. A finite group \(X\) acting on \(V(\Gamma)\) \textit{preserves the structure of \(\Gamma\)} if two vertices of \(\Gamma\) are adjacent iff their images under every element of \(X\) are adjacent. \(\Gamma\) is \textit{\((X,s)\)-arc-transitive} if, in addition, \(X\) is transitive on \(V(\Gamma)\) and on the set of \(s\)-arcs of \(\Gamma\). Then, a partition \(\mathcal B\) of \(V(\Gamma)\) is \textit{\(X\)-invariant} if \(\{\sigma^x|\sigma\in B\}\in \mathcal B\) for any \(B\in\mathcal B\) and any \(x\in X\). A finite \(X\)-symmetric graph \(\Gamma\) is \textit{imprimitive} if \(V(\Gamma)\) admits an \(X\)-invariant partition \(\mathcal B\) having some \(B\in\mathcal B\) with \(1<|B|<|V(\Gamma)|\); then the \textit{quotient graph} \(\Gamma_{\mathcal B}\) has vertex set \(\mathcal B\), in which two blocks are adjacent iff there exists at least one edge of \(\Gamma\) between them. Let \(\Sigma\) be a finite \(X\)-symmetric graph of valency \(\overline{b}\geq 2\). A \textit{star} is a set of \(\ell\)-arcs starting from the same vertex of \(\Sigma\), where \(\ell\geq1\). From the author's abstract: ``We give a sufficient and necessary condition for the existence of a class of finite, imprimitive \((X,s)\)-arc-transitive graphs which have a quotient isomorphic to \(\Sigma\) and are not multicovers of that quotient, together with a combinatorial method, called the \textit{double-star graph construction}, for constructing such graphs. Moreover, for any \(X\)-symmetric graph \(\Gamma\) admitting a nontrivial \(X\)-invariant partition \(\mathcal B\) such that \(\Gamma\) is not a multicover of \(\Gamma_{\mathcal B}\), we show that there exists a sequence of \(m+1\) \(X\)-invariant partitions \({\mathcal B}={\mathcal B}_0\), \({\mathcal B}_1\), \dots \({\mathcal B}_m\) of \(V(\Gamma)\), where \(m\geq1\) is an integer, such that \({\mathcal B}_i\) is a proper refinement of \({\mathcal B}_{i-1}\), and \(\Gamma_{{\mathcal B}_{i}}\) can be reconstructed from \(\Gamma_{{\mathcal B}_{i-1}}\) by the double-star graph construction for \(i=1,2,\dots m\), and that either \(\Gamma\cong\Gamma_{{\mathcal B}_m}\) or \(\Gamma\) is a multicover of \(\Gamma_{{\mathcal B}_m}\).''
0 references
symmetric graph
0 references
imprimitive graph
0 references
multicover
0 references
quotient graph
0 references
double-star graph
0 references
\(s\)-arc-transitive graph
0 references