О нижней оценке числа связного доминирования в графах с фиксированной степенной последовательностью

Автор: Курносов А.Д.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 2 (46) т.12, 2020 года.

Бесплатный доступ

Числом связного доминирования yc(G) связного графа G называется минимальный размер доминирующего множества вершин, порождающего связный подграф в G. По-другому можно определить yc(G) как наименьшее количество нелистовых вершин в остовных деревьях графа G. В работе получены некоторые достижимые нижние оценки величины yc(G) для графов, имеющих заданную последовательность степеней вершин. В частности, рассмотрены регулярные графы и бирегулярные графы с листьями.

Графы, степенная последовательность, регулярные графы, бирегулярные графы, связное доминирование, реализующий граф, нижняя оценка, остовное дерево, остовное дерево с максимальным числом листьев

Короткий адрес: https://sciup.org/142230078

IDR: 142230078

Список литературы О нижней оценке числа связного доминирования в графах с фиксированной степенной последовательностью

Diestel R. Graph Theory 5th edition. Heidelberg : Springer-Verlag, Graduate Texts in Mathematics, 2016. V. 173.
Емеличев B.A., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. Москва : Наука. Физматлит, 1990.
Havel V. A remark on the existence of finite graphs (Czech.) // Cas. Pestovani Mat. 1955. V. 80. P. 477-480.
Hakimi S. On the readability of a set of integers as degrees of the vertices of a graph // SIAM J. Appl. Math. 1962. V. 10. P. 496-506.
Erdos P., Gallai T. Grafok eloirt fokszamii pontokkal // Matematikai Lapok. 1960. V. 11. P. 26 i 27 i.
Haynes T.W., Hedetniemi S.T., Slater P.J. Fundamentals of Domination in Graphs. New York : Marcel Dekker, Inc., Monographs and textbooks in Pure and Applied Mathematics, 1998.
Визит В.Г. Некоторые нерешённые задачи в теории графов // Успехи мат. наук. 1968. Т. 23. С. 117-134.
Lemke P. The maximum-leaf spanning tree problem in cubic graphs is NP-complete // IMA Preprint Series, 1988. N 428.
Zelinka B. Finding a Spanning Tree of a Graph with Maximal Number of Terminal Vertices // Kvbernetika. 1973. V. 9, N 5. P. 357-360.
Storer J.A. Constructing full spanning trees for cubic graphs // Inform. Process. Lett. 1981. V. 13, N 1, I. 1. P. 8-11.
Griggs J.R., Kleitman D.J., Shastri A. Spanning trees with many leaves in cubic graphs // Journal of Graph Theory. 1989. V. 13, N 6. P. 669-695.
Kleitman D.J., WestD.B. Spanning trees with many leaves // SIAM J. Discrete Math. 1991. V. 4, I. 1. P. 99-106.
Griggs J.R., Wu M. Spanning trees in graphs of minimum degree 4 or 5 // Discrete Mathematics. 1992. V. 104, I. 2. P. 167-183.
Fusco E., Monti A. Spanning Trees with Many Leaves in Regular Bipartite Graphs // Proc. of the 18th International Symposium on Algorithms and Computation. 2007. Lecture Notes in Computer Science. V. 4835. P. 904-914.
Bonsma P., Zickfeld F. Spanning trees with many leaves in graphs without diamonds and blossoms // Proc. of the 8th Latin American Symposium on Theoretical Informatics. 2008. Lecture Notes in Computer Science. V. 4957. P. 531-543.
Гравип H.B. Построение остовного дерева графа с большим количеством листьев // Зап. научн. семин. ПОМИ. 2010. Т. 381. С. 31-46.
Bankevich А. V., Karpov D. V. Bounds of the number of leaves of spanning trees //J. Math. Sci. 2012. V. 184. P. 564-572.
Карпов Д.В. Нижние оценки количества листьев в остовных деревьях // Зап. научн. сем. ПОМИ. 2016. Т. 450. С. 62-73.
Симарова, Е.Н. Оценка количества листьев в остовном дереве связного графа с минимальной степенью 6 // Зап. научн. сем. ПОМИ. 2017. Т. 464. С. 112 131.
Sampathkumar Е., Walikar H.B. The connected domination number of a graph //J. Math. Phvs. Sci. 1979. V. 13, N 6. P. 607-613.
Hedetniemi S.T., Laskar R.C. Connected domination in Graphs // Proc. of the Cambridge Combinatorial Conference in honour of Paul Erdos on Graph Theory and Combinatorics. 1984. P. 209-218.
Caro Y., WestD.B., Yuster R. Connected domination and spanning trees with many leaves // SIAM J. Discrete Math. 2000. V. 13, I. 2. P. 202-211.
Gayathri M. Connected domination in graphs // Graduate Theses and Dissertations. 2005. https://scholarcommons.usf.edu/etd/2961
Duckwortha W., Mans B. Connected domination of regular graphs // Discrete Math. 2009. V. 309, I. 8. P. 2305-2322.
Desormeaux W.J., Haynes T.W., Henning M.A. Bounds on the connected domination number of a graph 11 Discrete Appl. Math. 2013. V. 161, I. 18. P. 2925-2931.
Das B.,Bhargavan V. Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets // Proc. of the 6th International Conference on Communications. 2002. IEEE Xplore. V. 1. P. 376-380.
Alzoubi K.M., Wan P.J, Frieder O. New distributed algorithm for connected dominating set in wireless ad hoc networks // Proc. of the 35th Annual Hawaii International Conference on System Sciences. 2002. IEEE Xplore. P. 3849-3855.
Du D.Z., Wan P.J. Connected dominating set: theory and applications. New York: Springer, Springer Optimization and Its Applications, 2013. V. 77.
Gentner M., Henning M., Rautenbach D. Largest domination number and smallest independence number of forests with given degree sequence // Discrete Applied Mathematics. 2016. V. 206. P. 181-187.
Gentner M., Henning M., Rautenbach D. Smallest domination number and largest independence number of graphs and forests with given degree sequence // Journal of Graph Theory. 2018. V. 88, I. 1. P. 131-145.
Курносое А.Д. Множество всех возможных значений числа доминирования в деревьях с заданной степенной последовательностью // Дискретный анализ и исследование операций. 2020. Т. 27, № 1. С. 61-87.
Курносов А.Д., Дайняк А.Б. Независимые множества в деревьях с заданными степенными последовательностями // Труды IX Международной конференции «Дискретные модели в теории управляющих систем». 2015. С. 141-142.
Kaspar S., Gayathri В., Kulandaivel М.Р., Shobanadevi N. Towards connected domination in graphs // International Journal of Pure and Applied Mathematics. 2017. V. 117, N 14. P. 53-62.

Еще

Статья научная