On transitive decompositions of disconnected graphs (Q1043542)

From MaRDI portal
Revision as of 23:13, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
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
    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

    Identifiers