Switching $(m, n)$-mixed graphs with respect to Abelian groups
| Title: | Switching $(m, n)$-mixed graphs with respect to Abelian groups |
|---|---|
| Authors: | Leclerc, E., MacGillivray, G., Warren, J. M. |
| Publication Year: | 2021 |
| Collection: | Mathematics |
| Subject Terms: | Mathematics - Combinatorics, 05C15, 68R10 |
| More Details: | We extend results of Brewster and Graves for switching $m$-edge coloured graphs with respect to a cyclic group to switching $(m, n)$-mixed graphs with respect to an Abelian group. In particular, we establish the existence of a $(m, n)$-mixed graph $P_\Gamma(H)$ with the property that a $(m, n)$-mixed graph $G$ is switch equivalent to $H$ if and only if it is a special subgraph of $P_\Gamma(H)$, and the property that that $G$ can be switched to have a homomorphism to $H$ if and only if it has a homomorphism (without switching) to $P_\Gamma(H)$. We consider the question of deciding whether a $(m, n)$-mixed graph can be switched so that it has a homomorphism to a proper subgraph, i.e. whether it can be switched so that it isn't a core. We show that this question is NP-hard for arbitrary groups and NP-complete for Abelian groups. Finally, we consider the complexity of the switchable $k$-colouring problem for $(m, n)$-mixed graphs and prove a dichotomy theorem in the cases where $m \geq 1$. |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2110.01576 |
| Accession Number: | edsarx.2110.01576 |
| Database: | arXiv |
| FullText | Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/2110.01576 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20211004&spage=&pages=&title=Switching $(m, n)$-mixed graphs with respect to Abelian groups&atitle=Switching%20%24%28m%2C%20n%29%24-mixed%20graphs%20with%20respect%20to%20Abelian%20groups&aulast=Leclerc%2C%20E.&id=DOI: Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries |
|---|---|
| Header | DbId: edsarx DbLabel: arXiv An: edsarx.2110.01576 RelevancyScore: 1022 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 1021.66485595703 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Switching $(m, n)$-mixed graphs with respect to Abelian groups – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Leclerc%2C+E%2E%22">Leclerc, E.</searchLink><br /><searchLink fieldCode="AR" term="%22MacGillivray%2C+G%2E%22">MacGillivray, G.</searchLink><br /><searchLink fieldCode="AR" term="%22Warren%2C+J%2E+M%2E%22">Warren, J. M.</searchLink> – Name: DatePubCY Label: Publication Year Group: Date Data: 2021 – Name: Subset Label: Collection Group: HoldingsInfo Data: Mathematics – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Mathematics+-+Combinatorics%22">Mathematics - Combinatorics</searchLink><br /><searchLink fieldCode="DE" term="%2205C15%2C+68R10%22">05C15, 68R10</searchLink> – Name: Abstract Label: Description Group: Ab Data: We extend results of Brewster and Graves for switching $m$-edge coloured graphs with respect to a cyclic group to switching $(m, n)$-mixed graphs with respect to an Abelian group. In particular, we establish the existence of a $(m, n)$-mixed graph $P_\Gamma(H)$ with the property that a $(m, n)$-mixed graph $G$ is switch equivalent to $H$ if and only if it is a special subgraph of $P_\Gamma(H)$, and the property that that $G$ can be switched to have a homomorphism to $H$ if and only if it has a homomorphism (without switching) to $P_\Gamma(H)$. We consider the question of deciding whether a $(m, n)$-mixed graph can be switched so that it has a homomorphism to a proper subgraph, i.e. whether it can be switched so that it isn't a core. We show that this question is NP-hard for arbitrary groups and NP-complete for Abelian groups. Finally, we consider the complexity of the switchable $k$-colouring problem for $(m, n)$-mixed graphs and prove a dichotomy theorem in the cases where $m \geq 1$. – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2110.01576" linkWindow="_blank">http://arxiv.org/abs/2110.01576</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.2110.01576 |
| PLink | https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2110.01576 |
| RecordInfo | BibRecord: BibEntity: Subjects: – SubjectFull: Mathematics - Combinatorics Type: general – SubjectFull: 05C15, 68R10 Type: general Titles: – TitleFull: Switching $(m, n)$-mixed graphs with respect to Abelian groups Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Leclerc, E. – PersonEntity: Name: NameFull: MacGillivray, G. – PersonEntity: Name: NameFull: Warren, J. M. IsPartOfRelationships: – BibEntity: Dates: – D: 04 M: 10 Type: published Y: 2021 |
| ResultId | 1 |