Back to Search
Start Over
Further results on the deficiency of graphs.
- Source :
-
Discrete Applied Mathematics . Jul2017, Vol. 226, p117-126. 10p. - Publication Year :
- 2017
-
Abstract
- A proper t -edge-coloring of a graph G is a mapping α : E ( G ) → { 1 , … , t } such that all colors are used, and α ( e ) ≠ α ( e ′ ) for every pair of adjacent edges e , e ′ ∈ E ( G ) . If α is a proper edge-coloring of a graph G and v ∈ V ( G ) , then the spectrum of a vertex v , denoted by S ( v , α ) , is the set of all colors appearing on edges incident to v . The deficiency of α at vertex v ∈ V ( G ) , denoted by d e f ( v , α ) , is the minimum number of integers which must be added to S ( v , α ) to form an interval, and the deficiency d e f ( G , α ) of a proper edge-coloring α of G is defined as the sum ∑ v ∈ V ( G ) d e f ( v , α ) . The deficiency of a graph G , denoted by d e f ( G ) , is defined as follows: d e f ( G ) = min α d e f ( G , α ) , where minimum is taken over all possible proper edge-colorings of G . For a graph G , the smallest and the largest values of t for which it has a proper t -edge-coloring α with deficiency d e f ( G , α ) = d e f ( G ) are denoted by w d e f ( G ) and W d e f ( G ) , respectively. In this paper, we obtain some bounds on w d e f ( G ) and W d e f ( G ) . In particular, we show that for any l ∈ N , there exists a graph G such that d e f ( G ) > 0 and W d e f ( G ) − w d e f ( G ) ≥ l . It is known that for the complete graph K 2 n + 1 , d e f ( K 2 n + 1 ) = n ( n ∈ N ). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Hałuszczak posed the following conjecture on the deficiency of near-complete graphs: if n ∈ N , then d e f ( K 2 n + 1 − e ) = n − 1 . In this paper, we confirm this conjecture. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH grammars
*SPECTRUM analysis
*OPTICS
*QUALITATIVE chemical analysis
*INTEGERS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 226
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 123464364
- Full Text :
- https://doi.org/10.1016/j.dam.2017.04.005