×

Pell graphs. (English) Zbl 1418.05098

Summary: In this paper, we introduce the Pell graphs, a new family of graphs similar to the Fibonacci cubes. They are defined on certain ternary strings (Pell strings) and turn out to be subgraphs of Fibonacci cubes of odd index. Moreover, as well as ordinary hypercubes and Fibonacci cubes, Pell graphs have several interesting structural and enumerative properties. Here, we determine some of them. Specifically, we obtain a canonical decomposition giving a recursive structure, some basic properties (bipartiteness and existence of maximal matchings), some metric properties (radius, diameter, center, periphery, medianicity), some properties on subhypercubes (cube coefficients and polynomials, cube indices, decomposition in subhypercubes), and, finally, the distribution of the degrees.

MSC:

05C65 Hypergraphs
05C12 Distance in graphs

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Asratian, A. S.; Denley, T. M.J.; Hääggkvist, R., (Bipartite Graphs and Their Applications. Bipartite Graphs and Their Applications, Cambridge Tracts in Mathematics, 131 (1998), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0914.05049
[2] Bergeron, F.; Labelle, G.; Leroux, P., (Combinatorial Species and Tree-like Structures. Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and Its Applications, 67 (1998), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0888.05001
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001
[4] Brešar, B.; Klavžar, S.; Škrekovski, R., The cube polynomial and its derivatives: the case of median graphs, Electron. J. Combin., 10 (2003) · Zbl 1020.05035
[5] Buckley, F.; Harary, F., Distance in Graphs (1990), Addison-Wesley: Addison-Wesley Redwood City · Zbl 0688.05017
[6] Buckley, F.; Harary, F., Unsolved problems on distance in graphs, (Electron. Notes Discrete Math., 11 (2002), Elsevier: Elsevier Amsterdam) · Zbl 1075.05521
[7] Comtet, L., Advanced Combinatorics (1974), Reidel, Dordrecht-Holland: Reidel, Dordrecht-Holland Boston
[8] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001
[9] Hahn, G.; Tardif, C., Graph homomorphisms: structure and symmetry, (G. Hahn, G. Sabidussi, Graph Symmetry (1997), Kluver), 107-166 · Zbl 0880.05079
[10] Hautus, M. L.J.; Klarner, D. A., The diagonal of a double power series, Duke Math. J., 38, 229-235 (1971) · Zbl 0214.08304
[11] Hsu, W.-J., Fibonacci cubes – a new computer architecture for parallel processing, (Technical Report CPS-90-04 (1990), Michigan State University)
[12] Hsu, W.-J., Fibonacci cubes – a new interconnection topology, IEEE Trans. on Parallel and Distributed Systems, 4, 3-12 (1993)
[13] Ilićc, A.; Klavžar, S.; Rho, Y., Generalized fibonacci cubes, Discrete Math., 312, 2-11 (2012) · Zbl 1233.05165
[14] Ilićc, A.; Klavžar, S.; Rho, Y., Generalized lucas cubes, Appl. Anal. Discrete Math., 6, 82-94 (2012) · Zbl 1289.05124
[15] Imrich, W.; Klavžar, S., (Product Graphs. Structure and Recognition. Product Graphs. Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization (2000), Wiley-Interscience: Wiley-Interscience New York)
[16] Klavžar, S., On median nature and enumerative properties of fibonacci-like cubes, Discrete Math., 299, 145-153 (2005) · Zbl 1073.05007
[17] Klavžar, S., Structure of fibonacci cubes: a survey, J. Comb. Optim., 25, 505-522 (2013) · Zbl 1273.90173
[18] Klavžar, S.; Mollard, M., Cube polynomial of fibonacci and lucas cubes, Acta Appl. Math., 117, 93-105 (2012) · Zbl 1235.05071
[19] Klavžar, S.; Mollard, M.; Petkovšek, M., The degree sequence of fibonacci and lucas cubes, Discrete Math., 311, 1310-1322 (2011) · Zbl 1225.05132
[20] Liu, J.; Hsu, W.-J.; Chung, M. J., Generalized fibonacci cubes are mostly hamiltonian, J. Graph Theory, 18, 817-829 (1994) · Zbl 0816.05041
[21] Liu, L. L.; Wang, Y., A unified approach to polynomial sequences with only real zeros, Adv. Appl. Math., 38, 542-560 (2007) · Zbl 1123.05009
[22] Mulder, M., The structure of median graphs, Discrete Math., 24, 197-204 (1978) · Zbl 0394.05038
[23] Munarini, E.; Perelli Cippo, C.; Zagaglia Salvi, N., On the lucas cubes, Fibonacci Quart., 39, 12-21 (2001) · Zbl 0987.05048
[24] Munarini, E.; Zagaglia Salvi, N., Structural and enumerative properties of the fibonacci cubes, Discrete Math., 255, 317-324 (2002) · Zbl 1008.05048
[25] Munarini, E.; Zagaglia Salvi, N., On fibonacci-like cubes, Rend. Sem. Mat. Messina Ser. II, 9, 185-199 (2003) · Zbl 1124.05310
[26] Quian, H.; Wu, J., Enhanced fibonacci cubes, Comput. J., 39, 331-345 (1996)
[27] Shapiro, L. W.; Getu, S.; Woan, W. J.; Woodson, L. C., The riordan group, Discrete Appl. Math., 34, 229-239 (1991) · Zbl 0754.05010
[28] N.J.A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org/; N.J.A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org/ · Zbl 1044.11108
[29] Whitehead, C.; Zagaglia Salvi, N., Extended lucas cubes, Util. Math., 71, 13-21 (2006) · Zbl 1111.05057
[30] Wilf, H. S., Generating Functionology (1990), Academic Press: Academic Press Boston
[31] Wu, J., Extended fibonacci cubes, IEEE Trans. Parallel Distributed Systems, 8, 12, 3-9 (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.