On transitive decompositions of disconnected graphs (Q1043542): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:59, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On transitive decompositions of disconnected graphs |
scientific article |
Statements
On transitive decompositions of disconnected graphs (English)
0 references
9 December 2009
0 references
Let \(\Gamma\) be a graph (directed or undirected) and \(\mathcal P\) an edge-decomposition of \(\Gamma\). A subgroup \(G\) of the automorphism group \(\text{Aut}\Gamma\) preserves \(\mathcal P\) if for all \(g\in G\) and \(P\in \mathcal P\) it is true that \(P^g\in \mathcal P\). The pair \((\Gamma, \mathcal P)\) is then called a \(G\)-decomposition of \(\Gamma\). If \(G\) induces a transitive action on \(\mathcal P\) (that is, if for all \(P, P'\in\mathcal P\) there exists \(g\in G\) with \(P^g=P'\)), then \((\Gamma, \mathcal P)\) is a \(G\)-transitive decomposition. A homogeneous factorization is a \(G\)-transitive decomposition \((\Gamma, \mathcal P)\) such that the kernel of the \(G\)-action on \(\mathcal P\) has a subgroup \(M\) that acts transitively on the arc set of \(\Gamma\). It is shown that restricting a transitive decomposition of a disconnected graph \(\Gamma\) to a connected component \(\Delta\) can produce an arbitrary partition of the arc set of \(\Delta\), even if all the connected components of \(\Gamma\) are isomorphic. Moreover, it is shown that any collection of transitive decompositions of connected graphs can arise as a subset of the restrictions of a transitive decomposition of a disconnected graph into its connected components. It is further proved that the restriction of a homogeneous factorization of a disconnected graph to a connected component is itself a homogeneous factorization, and moreover, restrictions to different connected components are mutually isomorphic (as transitive decompositions). Finally, a simple characterization of \(G\)-transitive decompositions whose restriction to a connected component \(\Delta\) is transitive on that component is given.
0 references
disconnected graph
0 references
transitive decomposition
0 references
homogeneous factorisation
0 references