More relations between $λ$-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917603214098432 |
|---|---|
| author | Zaker, Manouchehr |
| author_facet | Zaker, Manouchehr |
| contents | This paper deals with the $λ$-labeling and $L(2,1)$-coloring of simple graphs. A $λ$-labeling of a graph $G$ is any labeling of the vertices of $G$ with different labels such that any two adjacent vertices receive labels which differ at least two. Also an $L(2,1)$-coloring of $G$ is any labeling of the vertices of $G$ such that any two adjacent vertices receive labels which differ at least two and any two vertices with distance two receive distinct labels. Assume that a partial $λ$-labeling $f$ is given in a graph $G$. A general question is whether $f$ can be extended to a $λ$-labeling of $G$. We show that the extension is feasible if and only if a Hamiltonian path consistent with some distance constraints exists in the complement of $G$. Then we consider line graph of bipartite multigraphs and determine the minimum number of labels in $L(2,1)$-coloring and $λ$-labeling of these graphs. In fact we obtain easily computable formulas for the path covering number and the maximum path of the complement of these graphs. We obtain a polynomial time algorithm which generates all Hamiltonian paths in the related graphs. A special case is the Cartesian product graph $K_n\Box K_n$ and the generation of $λ$-squares. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_13919 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | More relations between $λ$-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs Zaker, Manouchehr Combinatorics Discrete Mathematics 05C85, 05C38, 05C15, 05C45 This paper deals with the $λ$-labeling and $L(2,1)$-coloring of simple graphs. A $λ$-labeling of a graph $G$ is any labeling of the vertices of $G$ with different labels such that any two adjacent vertices receive labels which differ at least two. Also an $L(2,1)$-coloring of $G$ is any labeling of the vertices of $G$ such that any two adjacent vertices receive labels which differ at least two and any two vertices with distance two receive distinct labels. Assume that a partial $λ$-labeling $f$ is given in a graph $G$. A general question is whether $f$ can be extended to a $λ$-labeling of $G$. We show that the extension is feasible if and only if a Hamiltonian path consistent with some distance constraints exists in the complement of $G$. Then we consider line graph of bipartite multigraphs and determine the minimum number of labels in $L(2,1)$-coloring and $λ$-labeling of these graphs. In fact we obtain easily computable formulas for the path covering number and the maximum path of the complement of these graphs. We obtain a polynomial time algorithm which generates all Hamiltonian paths in the related graphs. A special case is the Cartesian product graph $K_n\Box K_n$ and the generation of $λ$-squares. |
| title | More relations between $λ$-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs |
| topic | Combinatorics Discrete Mathematics 05C85, 05C38, 05C15, 05C45 |
| url | https://arxiv.org/abs/2111.13919 |