Graph theory; Combinatorics on words; Induced subtrees; Leaf; Prefix normal word; Prefix normal form
Abstract :
[en] Given a simple graph G with n vertices and a natural number i<n+1, let be L(i) the maximum number of leaves that can be realized by an induced subtree T of G with i vertices. We introduce a problem that we call the leaf realization problem, which consists in deciding whether, for a given sequence of n+1 natural numbers (l_0,l_1,...,l_n), there exists a simple graph G with n vertices such that L(i)=l_i for i=0,...,n . We present basic observations on the structure of these sequences for general graphs and trees. In the particular case where G is a caterpillar graph, we exhibit a bijection between the set of the discrete derivatives and the set of prefix normal words.
Disciplines :
Mathematics
Author, co-author :
Blondin Massé, Alexandre; Université du Québec à Montréal
De Carufel, Julien; Université du Québec à Trois Rivières
Goupil, Alain; Université du Québec à Trois Rivières
Lapointe, Mélodie; Université du Québec à Montréal
Nadeau, Émile; Université du Québec à Montréal
Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Probabilités et statistique mathématique
Language :
English
Title :
Leaf realization problem, caterpillar graphs and prefix normal words
Deepak, A., Fernández-Baca, D., Tirthapura, S., Sanderson, M.J., McMahon, M.M., EvoMiner: frequent subtree mining in phylogenetic databases. Knowl. Inf. Syst. 41:3 (2014), 559–590.
Erdős, P., Saks, M., Sós, V.T., Maximum induced trees in graphs. J. Combin. Theory Ser. B 41:1 (1986), 61–79.
Zaki, M.J., Efficiently mining frequent trees in a forest. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, 2002, ACM, New York, NY, USA, 71–80.
Payan, C., Tchuente, M., Xuong, N.H., Arbres avec un nombre maximum de sommets pendants (Trans.) Trees with a maximal number of vertices with degree 1 Discrete Math. 49:3 (1984), 267–273.
Garey, M.R., Johnson, D.S., Computers and Intractability. 1979, W.H. Freeman and Co., San Francisco, Calif.
Boukerche, A., Cheng, X., Linus, J., A performance evaluation of a novel energy-aware data-centric routing algorithm in wireless sensor networks. Wirel. Netw. 11:5 (2005), 619–635.
Chen, S., Ljubić, I., Raghavan, S., The generalized regenerator location problem. INFORMS J. Comput. 27:2 (2015), 204–220.
Blondin Massé, A., de Carufel, J., Goupil, A., Samson, M., Fully leafed tree-like polyominoes and polycubes. Combinatorial Algorithms, 28th International Workshop, IWOCA 2017, Newcastle, NSW, Australia Lecture Notes in Comput. Sci., vol. 10765, 2018, Springer, 206–218, 10.1007/978-3-319-78825-87.
A. Blondin Massé, J. de Carufel, A. Goupil, M. Lapointe, É. Nadeau, É. Vandomme, Fully leafed induced subtrees, arxiv.org/abs/1709.09808, 2017.
Erdős, P., Gallai, T., Gráfok előírt fokú pontokkal (Trans.) Graphs with prescribed degrees of vertices Mat. Lapok 11 (1961), 264–274.
Havel, V., Poznámka o existenci konečných grafů (Trans.) A remark on the existence of finite graphs Čas. Pěst. Mat. 080:4 (1955), 477–480.
Hakimi, S.L., On realizability of a set of integers as degrees of the vertices of a linear graph. I. J. Soc. Ind. Appl. Math. 10:3 (1962), 496–506.
Gale, D., A theorem on flows in networks. Pacific J. Math. 7:2 (1957), 1073–1082.
Ryser, H.J., Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9 (1957), 371–377.
Kleitman, D.J., Wang, D.-L., Algorithms for constructing graphs and digraphs with given valences and factors. Discrete Math. 6:1 (1973), 79–88.
Fulkerson, D., Zero-one matrices with zero trace. Pacific J. Math. 10:3 (1960), 831–836.
Chen, W.-K., On the realization of a (p,s)-digraph with prescribed degrees. J. Franklin Inst. 281:5 (1966), 406–422.
Anstee, R.P., Properties of a class of (0,1)-matrices covering a given matrix. Canad. J. Math. 34:2 (1982), 438–453.
Berger, A., A note on the characterization of digraphic sequences. Discrete Math. 314 (2014), 38–41.
Fici, G., Lipták, Z., On prefix normal words. Proceedings of the 15th International Conference on Developments in Language Theory (DLT 2011) Lecture Notes in Comput. Sci., vol. 6795, 2011, Springer, 228–238.
Burcsi, P., Fici, G., Lipták, Z., Ruskey, F., Sawada, J., On prefix normal words and prefix normal forms. Theoret. Comput. Sci. 659 (2017), 1–13.
Burcsi, P., Fici, G., Lipták, Z., Ruskey, F., Sawada, J., On combinatorial generations on prefix normal words. Proceedings of the 28th Ann. Symp. on Comb. Pattern Matching (CPM 2014) Lecture Notes in Comput. Sci., vol. 8486, 2014, Springer, Cham, 60–69.
Prüfer, H., Neuer Beweis eines Satzes über Permutationen (Trans.) A new proof of a theorem on permutations Arch. Math. Phys. 27 (1918), 742–744.
Kitaev, S., Lozin, V., Words and Graphs. 2015, Springer, Cham.
Diestel, R., Graph Theory. 4th edition Grad. Texts in Math., vol. 173, 2010, Springer, Heidelberg.
Lothaire, M., Combinatorics on Words. Cambridge Math. Lib., 1997, Cambridge University Press, Cambridge.
Harary, F., Schwenk, A.J., The number of caterpillars. Discrete Math. 6:4 (1973), 359–365.
