Maximal independent sets in graphs with at most one cycle

被引：35

作者：

Jou, MJ ^{[1
]}

Chang, GJ ^{[1
]}

机构：

[1] NATL CHIAO TUNG UNIV,DEPT MATH APPL,HSINCHU 30050,TAIWAN

来源：

DISCRETE APPLIED MATHEMATICS | 1997年 / 79卷 / 1-3期

关键词：

(maximal) independent set; cycle; connected graph; isolated vertex; leaf; baton;

D O I：

10.1016/S0166-218X(97)00033-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we determine the largest number of maximal independent sets among all connected graphs of order n, which contain at most one cycle. We also characterize those extremal graphs achieving this maximum value. As a consequence, the corresponding results for graphs with at most one cycle but not necessarily connected are also given.

引用

页码：67 / 73

页数：7

共 50 条

[21] Maximal independent sets in minimum colorings
Arumugam, S.
Haynes, Teresa W.
Henning, Michael A.
Nigussie, Yared
DISCRETE MATHEMATICS, 2011, 311 (13) : 1158 - 1163
[22] Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
Endre Boros
Khaled Elbassioni
Vladimir Gurvich
Leonid Khachiyan
Mathematical Programming, 2003, 98 : 355 - 368
[23] Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices
Boros, E
Elbassioni, K
Gurvich, V
Khachiyan, L
MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) : 355 - 368
[24] Counting Non-Isomorphic Maximal Independent Sets of the n-Cycle Graph
Bisdorff, Raymond
Marichal, Jean-Luc
JOURNAL OF INTEGER SEQUENCES, 2008, 11 (05)
[25] On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
Barbosa, Rommel
Cappelle, Marcia R.
Rautenbach, Dieter
DISCRETE MATHEMATICS, 2013, 313 (16) : 1630 - 1635
[26] Maximal independent sets in a generalisation of caterpillar graph
K. S. Neethi
Sanjeev Saxena
Journal of Combinatorial Optimization, 2017, 33 : 326 - 332
[27] Maximal independent sets in the covering graph of the cube
Duffus, Dwight
Frankl, Peter
Roedl, Vojtech
DISCRETE APPLIED MATHEMATICS, 2013, 161 (09) : 1203 - 1208
[28] Maximal independent sets in a generalisation of caterpillar graph
Neethi, K. S.
Saxena, Sanjeev
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (01) : 326 - 332
[29] The Maximal 2-independent Sets in Trees
Jou, Min-Jen
Lin, Jenq-Jong
PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON APPLIED MATHEMATICS, SIMULATION AND MODELLING, 2016, 41 : 106 - 109
[30] A representation diagram for maximal independent sets of a graph
Taki, M
Masuda, S
Kashiwabara, T
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1998, E81A (05) : 784 - 788

← 1 2 3 4 5 →