Back
 OJDM  Vol.9 No.1 , January 2019
Equivalence between Linear Tangle and Maximal Single Ideal
Abstract: The concept of linear tangle was introduced as an obstruction to mixed searching number. The concept of single ideal has been introduced as an obstruction to linear-width. Moreover, it was already known that mixed search number is equivalent to linear-width. Hence, by combining those results, we obtain a proof of the equivalence between linear tangle and single ideal. This short report gives an alternative proof of the equivalence.
Cite this paper: Fujita, T. and Yamazaki, K. (2019) Equivalence between Linear Tangle and Maximal Single Ideal. Open Journal of Discrete Mathematics, 9, 7-10. doi: 10.4236/ojdm.2019.91002.
References

[1]   Aigner, M. and Fromme, M. (1984) A Game of Cops and Robbers. Discrete Applied Mathematics, 8, 1-12.
https://doi.org/10.1016/0166-218X(84)90073-8

[2]   Bonato, A. (2011) The Game of Cops and Robbers on Graphs. Vo. 12, The Student Mathematical Library.
https://doi.org/10.1090/stml/061

[3]   Bonato, A. and Yang, B.T. (2013) Graph Searching and Related Problems. In: Pardalos, P., Du, D.Z. and Graham, R., Eds., Handbook of Combinatorial Optimization, Springer, Berlin, 1511-1558.
https://doi.org/10.1007/978-1-4419-7997-1_76

[4]   Angelopoulos, S., Fraignaud, P., Fomin, F., Nisse, N. and Thilikos, D.M. (2017) Report on GRASTA 2017, 6th Workshop on Graph Searching, Theory and Applications, Anogia, Crete, Greece, April 10-13, 2017.
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01645614

[5]   Fomin, F.V. and Thilikos, D.M. (2008) An Annotated Bibliography on Guaranteed Graph Searching. Theoretical Computer Science, 399, 236-245.
https://doi.org/10.1016/j.tcs.2008.02.040

[6]   Thilikos, D.M. (2000) Algorithms and Obstructions for Linear-Width and Related Search Parameters. Discrete Applied Mathematics, 105, 239-271.
https://doi.org/10.1016/S0166-218X(00)00175-X

[7]   Bienstock, D. (1989) Graph Searching, Path-Width, Tree-Width and Related Problems (a Survey). In Reliability of Computer and Communication Networks, Vol. 5 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 33-50.

[8]   Fomin, F.V. and Thilikos, D.M. (2003) On the Monotonicity of Games Generated by Symmetric Submodular Functions. Discrete Applied Mathematics, 131, 323-335.
https://doi.org/10.1016/S0166-218X(02)00459-6

[9]   Fujita, T. and Yamazaki, K. (2017) Linear-Width and Single Ideal. The 20th Anniversary of the Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo University of Science, 29th August-1st September 2017, 110-111.
http://www.jcdcgg.u-tokai.ac.jp/JCDCG3_2017_abstracts.pdf

[10]   Geelen, J., Gerards, B., Robertson, N. and Whittle, G. (2006) Obstructions to Branch-Decomposition of Matroids. Journal of Combinatorial Theory, Series B, 96, 560-570.
https://doi.org/10.1016/j.jctb.2005.11.001

 
 
Top