Read More
Date: 19-5-2022
1580
Date: 15-5-2022
1211
Date: 4-3-2022
1373
|
The (upper) vertex independence number of a graph, often called simply "the" independence number, is the cardinality of the largest independent vertex set, i.e., the size of a maximum independent vertex set (which is the same as the size of a largest maximal independent vertex set). The independence number is most commonly denoted , but may also be written (e.g., Burger et al. 1997) or (e.g., Bollobás 1981).
The independence number of a graph is equal to the largest exponent in the graph's independence polynomial.
The lower independence number may be similarly defined as the size of a smallest maximal independent vertex set in (Burger et al. 1997).
The lower irredundance number , lower domination number , lower independence number , upper independence number , upper domination number , and upper irredundance number satsify the chain of inequalities
(1) |
(Burger et al. 1997).
The ratio of the independence number of a graph to its vertex count is known as the independence ratio of (Bollobás 1981).
For a connected regular graph on vertices with vertex degree and smallest graph eigenvalue ,
(2) |
(A. E. Brouwer, pers. comm., Dec. 17, 2012).
For the graph radius,
(3) |
(DeLa Vina and Waller 2002). Lovasz (1979, p. 55) showed that when is the path covering number,
(4) |
with equality for only complete graphs (DeLa Vina and Waller 2002).
The matching number of a graph is equal to the independence number of its line graph .
By definition,
(5) |
where is the vertex cover number of and its vertex count (West 2000).
Known value for some classes of graph are summarized below.
graph | OEIS | values | |
alternating group graph | A000000 | 1, 1, 4, 20, 120, ... | |
-Andrásfai graph () | A000027 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
-antiprism graph () | A004523 | 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ... | |
-Apollonian network | A000244 | 1, 3, 9, 27, 81, 243, 729, 2187, ... | |
complete bipartite graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
complete graph | 1 | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
complete tripartite graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
cycle graph () | A004526 | 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ... | |
empty graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
-folded cube graph () | A058622 | 1, 1, 4, 5, 16, 22, 64, 93, 256, ... | |
grid graph | A000982 | 1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ... | |
grid graph | A036486 | 1, 4, 14, 32, 63, 108, 172, 256, 365, 500, ... | |
-halved cube graph | A005864 | 1, 1, 4, 5, 16, 22, 64, 93, 256, ... | |
-Hanoi graph | A000244 | 1, 3, 9, 27, 81, 243, 729, 2187, ... | |
hypercube graph | A000079 | 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... | |
-Keller graph | A258935 | 4, 5, 8, 16, 32, 64, 128, 256, 512, ... | |
-king graph () | A008794 | 1, 4, 4, 9, 9, 16, 16, 25, 25 | |
-knight graph () | A030978 | 4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ... | |
Kneser graph | |||
-Mycielski graph | A266550 | 1, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ... | |
Möbius ladder () | A109613 | 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ... | |
odd graph | A000000 | 1, 1, 4, 15, 56, 210, 792, 3003, 11440, ... | |
-pan graph | A000000 | 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ... | |
path graph | A004526 | 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ... | |
prism graph () | A052928 | 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ... | |
-Sierpiński carpet graph | 4, 32, 256, ... | ||
-Sierpiński gasket graph | 1, 3, 6, 15, 42, ... | ||
star graph | A028310 | 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
triangular graph () | A004526 | 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ... | |
-web graph () | A032766 | 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ... | |
wheel graph | A004526 | 1, 2, 2, 3, 3, 4, 4, 5, 5, ... |
Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "IndependenceNumber"].
Bollobás, B. "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.
Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.
Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).
DeLa Vina, E. and Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.
Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.
Skiena, S. "Maximum Independent Set" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.
Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A000079/M1129, A000244/M2807, A000982/M1348, A004523, A004526, A005864/M1111, A008794, A028310, A030978, A032766, A036486, A052928, A058622, A109613, A258935, and A266550West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
|
|
علامات بسيطة في جسدك قد تنذر بمرض "قاتل"
|
|
|
|
|
أول صور ثلاثية الأبعاد للغدة الزعترية البشرية
|
|
|
|
|
مكتبة أمّ البنين النسويّة تصدر العدد 212 من مجلّة رياض الزهراء (عليها السلام)
|
|
|