- Moon-Moser 그래프와 완전그래프를 결합한 그래프의 극대독립집합의 개수
- ㆍ 저자명
- 정성진,이창수,Chung. S.J.,Lee. C.S.
- ㆍ 간행물명
- 대한산업공학회지
- ㆍ 권/호정보
- 1994년|20권 4호|pp.65-72 (8 pages)
- ㆍ 발행정보
- 대한산업공학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
An independent set of nodes is a set of nodes no two of which are joined by an edge. An independent set is called maximal if no more nodes can be added to the set without destroying its independence. The greatest number of maximal independent set is the maximum possible number of maximal independent set of a graph. We consider the greatest number of maximal independent set in connected graphs with fixed numbers of edges and nodes. For arbitrary number of nodes with a certain class of number of edges, we present the connected graphs with the greatest number of maximal independent set. For a given class of number of edges, the structure of graphs with the greatest number of maximal independent set is that the two components are completely joined; one consists of disjoint triangles as many as possible and the other is the complete graph with remaining nodes.