Premium
Graphs with given odd sets
Author(s) -
Chen Guantao,
Schelp Richard H.,
Šoltés Ľubomír
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199701)24:1<69::aid-jgt8>3.0.co;2-h
Subject(s) - combinatorics , mathematics , vertex (graph theory) , degree (music) , graph , set (abstract data type) , independent set , discrete mathematics , enhanced data rates for gsm evolution , order (exchange) , computer science , telecommunications , physics , finance , acoustics , economics , programming language
Given a graph G , its odd set is a set of all integers k such that G has odd number of vertices of degree k . We show that if two graphs G and H of the same order have the same odd sets then they can be obtained from each other by succesive application of the following two operations: • add or remove an edge joining two vertices of the same degree• replace two independent edges with two new independent edges on the same vertex set. If, moreover, both graphs G and H are regular or both are forests, it is sufficient to use only the first operation, but, in general, both operations are necessary. © 1997 John Wiley & Sons, Inc.