×

Hamming polynomials and their partial derivatives. (English) Zbl 1121.05115

A Hamming graph is a Cartesian product of complete graphs; its isometric subgraphs are partial Hamming graphs. The Hamming polynomial of a graph is its Hamming subgraphs counting polynomial. It is proven that any partial derivative of the Hamming polynomial of a partial Hamming graph is itself a Hamming polynomial of a graph, the \(K_k\)-derivate, for which an explicit construction is given. Further two combinatorial identities are derived for the diagonal Hamming polynomial coefficients of any power of a complete graph.

MSC:

05C99 Graph theory
05A19 Combinatorial identities, bijective combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bandelt, H.-J.; Mulder, H. M.; Wilkeit, E., Quasi-median graphs and algebras, J. Graph Theory, 18, 681-703 (1994) · Zbl 0810.05057
[2] Bandelt, H.-J.; Quintana-Murci, L.; Salas, A.; Macaumay, V., The fingerprint of phantom mutations in mitochondrial DNA data, American J. Human Genetics, 71, 1150-1160 (2002)
[3] Brešar, B., Partial Hamming graphs and expansion procedures, Discrete Math., 237, 13-27 (2001) · Zbl 0983.05070
[4] Brešar, B.; Klavžar, S.; Škrekovski, R., Quasi-median graphs, their generalizations, and tree-like equalities, European J. Combin., 24, 557-572 (2003) · Zbl 1022.05070
[5] Brešar, B.; Klavžar, S.; Škrekovski, R., The cube polynomial and its derivatives: The case of median graphs, Electron. J. Combin., 10, (#R3) 11 (2003) · Zbl 1020.05035
[6] B. Brešar, S. Klavžar, R. Škrekovski, On cube-free median graphs, Discrete Math. (in press); B. Brešar, S. Klavžar, R. Škrekovski, On cube-free median graphs, Discrete Math. (in press)
[7] Chung, F. R.K.; Graham, R. L.; Saks, M. E., A dynamic location problem for graphs, Combinatorica, 9, 111-131 (1989) · Zbl 0692.05055
[8] Chepoi, V., Isometric subgraphs of Hamming graphs and \(d\)-convexity, Cybernetics, 1, 6-11 (1988) · Zbl 0739.05035
[9] Djoković, D.Ž., Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267 (1973) · Zbl 0245.05113
[10] Garbano, M. L.; Malerba, J. F.; Lewinter, M., Hypercubes and Pascal’s triangle: A tale of two proofs, Math. Mag., 76, 216-217 (2003) · Zbl 1048.05005
[11] Imrich, W.; Klavžar, S., Product Graphs: Structure and Recognition (2000), John Wiley & Sons: John Wiley & Sons New York
[12] Klavžar, S., On the canonical metric representation, average distance, and partial Hamming graphs, European J. Combin., 27, 68-73 (2006) · Zbl 1078.05028
[13] S. Klavžar, Counting hypercubes in hypercubes, Discrete Math. (in press); S. Klavžar, Counting hypercubes in hypercubes, Discrete Math. (in press)
[14] Klavžar, S.; Mulder, H. M.; Škrekovski, R., An Euler-type formula for median graphs, Discrete Math., 187, 255-258 (1998) · Zbl 0957.05031
[15] Škrekovski, R., Two relations for median graphs, Discrete Math., 226, 351-353 (2001) · Zbl 0958.05043
[16] Soltan, P. S.; Chepoi, V., Solution of the Weber problem for discrete median metric spaces, Trudy Tbiliss. Mat. Inst. Razmadze Akad. Nauk Gruzin. SSR, 85, 52-76 (1987), (Russian)
[17] Wilkeit, E., Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B, 50, 179-197 (1990) · Zbl 0657.05023
[18] Winkler, P. M., Isometric embedding in products of complete graphs, Discrete Appl. Math., 7, 221-225 (1984) · Zbl 0529.05055
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.