Monochromatic $k$-connection of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929243251802112 |
|---|---|
| author | Cai, Qingqiong Fujita, Shinya Liu, Henry Park, Boram |
| author_facet | Cai, Qingqiong Fujita, Shinya Liu, Henry Park, Boram |
| contents | An edge-coloured path is monochromatic if all of its edges have the same colour. For a $k$-connected graph $G$, the monochromatic $k$-connection number of $G$, denoted by $mc_k(G)$, is the maximum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint monochromatic paths. In this paper, we shall study the parameter $mc_k(G)$. We obtain bounds for $mc_k(G)$, for general graphs $G$. We also compute $mc_k(G)$ exactly when $k$ is small, and $G$ is a graph on $n$ vertices, with a spanning $k$-connected subgraph having the minimum possible number of edges, namely $\lceil\frac{kn}{2}\rceil$. We prove a similar result when $G$ is a bipartite graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_09254 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Monochromatic $k$-connection of graphs Cai, Qingqiong Fujita, Shinya Liu, Henry Park, Boram Combinatorics An edge-coloured path is monochromatic if all of its edges have the same colour. For a $k$-connected graph $G$, the monochromatic $k$-connection number of $G$, denoted by $mc_k(G)$, is the maximum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint monochromatic paths. In this paper, we shall study the parameter $mc_k(G)$. We obtain bounds for $mc_k(G)$, for general graphs $G$. We also compute $mc_k(G)$ exactly when $k$ is small, and $G$ is a graph on $n$ vertices, with a spanning $k$-connected subgraph having the minimum possible number of edges, namely $\lceil\frac{kn}{2}\rceil$. We prove a similar result when $G$ is a bipartite graph. |
| title | Monochromatic $k$-connection of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.09254 |