The majority strategy on graphs
作者： Henry Martyn Mulder
DOI: 10.1016/S0166-218X(97)00072-3
关键词: Pathwidth 、 Combinatorics 、 Maximal independent set 、 Vertex (graph theory) 、 Mathematics 、 Discrete mathematics
摘要: In a tree one can find the median set of profile simply by starting at an arbitrary vertex and then moving to majority profile. This strategy is formulated for graphs. The graphs which this produces always M(E), each 7t, are precisely AMS C/ass$cication: Primary: 05C12,OSC75,05C99; secondary: 90B80
elsevier.com
sci-hub.se 参考文章(12)
Bohdan Zelinka, Medians and peripherians of trees Archivum Mathematicum. ,vol. 004, pp. 87- 95 ,(1968)
F.R.K. Chung, R.L. Graham, M.E. Saks, Dynamic Search in Graphs Discrete Algorithms and Complexity. pp. 351- 387 ,(1987) , 10.1016/B978-0-12-386870-1.50026-5
Rainer Bodendiek, Contemporary methods in graph theory Wissenschftsverlag. ,(1990)
Henry Martyn Mulder, The interval function of a graph ,(1980)
Sur les assemblages de lignes. Crelle's Journal. ,vol. 1869, pp. 185- 190 ,(1869) , 10.1515/CRLL.1869.70.185
H.J. Bandelt, J.P. Barthélemy, Medians in median graphs Discrete Applied Mathematics. ,vol. 8, pp. 131- 142 ,(1984) , 10.1016/0166-218X(84)90096-9
F.R. McMorris, Henry Martyn Mulder, Fred S. Roberts, The median procedure on median graphs Discrete Applied Mathematics. ,vol. 84, pp. 165- 181 ,(1998) , 10.1016/S0166-218X(98)00003-1
H.M. Mulder, A. Schrijver, Median Graphs and Helly hypergraphs Discrete Mathematics. ,vol. 25, pp. 41- 50 ,(1979) , 10.1016/0012-365X(79)90151-1
S. P. Avann, Metric ternary distributive semi-lattices Proceedings of the American Mathematical Society. ,vol. 12, pp. 407- 414 ,(1961) , 10.1090/S0002-9939-1961-0125807-5
Wilfried Imrich, Sandi Klavzar, On the complexity of recognizing Hamming graphs and related classes of graphs European Journal of Combinatorics. ,vol. 17, pp. 209- 221 ,(1996) , 10.1006/EUJC.1996.0018