Back to Search
Start Over
On the Neighbor-Distinguishing Indices of Planar Graphs.
- Source :
-
Bulletin of the Malaysian Mathematical Sciences Society . Mar2022, Vol. 45 Issue 2, p677-696. 20p. - Publication Year :
- 2022
-
Abstract
- Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any pair of adjacent vertices have different sets consisting of colors assigned on their incident edges. The neighbor-distinguishing index of G , denoted by χ a ′ (G) , is the minimum number of colors in such an edge coloring of G . In this paper, we show that if G is a connected planar graph with maximum degree Δ ≥ 14 , then Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. This improves a result in [W. Wang, D. Huang, A characterization on the adjacent vertex distinguishing index of planar graphs with large maximum degree, SIAM J. Discrete Math. 29(2015), 2412–2431], which says that every connected planar graph G with Δ ≥ 16 has Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANAR graphs
*GRAPH connectivity
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 01266705
- Volume :
- 45
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Bulletin of the Malaysian Mathematical Sciences Society
- Publication Type :
- Academic Journal
- Accession number :
- 155186120
- Full Text :
- https://doi.org/10.1007/s40840-021-01213-9