Large planar $(n,m)$-cliques
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908427865817088 |
|---|---|
| author | Bandopadhyay, Susobhan Sen, Sagnik Taruni, S |
| author_facet | Bandopadhyay, Susobhan Sen, Sagnik Taruni, S |
| contents | An \textit{$(n,m)$-graph} $G$ is a graph having both arcs and edges, and its arcs (resp., edges) are labeled using one of the $n$ (resp., $m$) different symbols. An \textit{$(n,m)$-complete graph} $G$ is an $(n,m)$-graph without loops or multiple edges in its underlying graph such that identifying any pair of vertices results in a loop or parallel adjacencies with distinct labels. We show that a planar $(n,m)$-complete graph cannot have more than $3(2n+m)^2+(2n+m)+1$ vertices, for all $(n,m) \neq (0,1)$ and that the bound is tight. This positively settles a conjecture by Bensmail \textit{et al.}~[Graphs and Combinatorics 2017]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_05678 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Large planar $(n,m)$-cliques Bandopadhyay, Susobhan Sen, Sagnik Taruni, S Combinatorics Discrete Mathematics An \textit{$(n,m)$-graph} $G$ is a graph having both arcs and edges, and its arcs (resp., edges) are labeled using one of the $n$ (resp., $m$) different symbols. An \textit{$(n,m)$-complete graph} $G$ is an $(n,m)$-graph without loops or multiple edges in its underlying graph such that identifying any pair of vertices results in a loop or parallel adjacencies with distinct labels. We show that a planar $(n,m)$-complete graph cannot have more than $3(2n+m)^2+(2n+m)+1$ vertices, for all $(n,m) \neq (0,1)$ and that the bound is tight. This positively settles a conjecture by Bensmail \textit{et al.}~[Graphs and Combinatorics 2017]. |
| title | Large planar $(n,m)$-cliques |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2409.05678 |