On transitive decompositions of disconnected graphs (Q1043542): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Homogeneous factorisations of graphs and digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transitive Decompositions of Graphs and Their Links with Geometry and Origami / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On classifying finite edge colored graphs with two transitive automorphism groups. / rank | |||
Normal rank |
Latest revision as of 07:14, 2 July 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