5
$\begingroup$

It is well-known (at least well-known enough to be on Wikipedia) that there are quite simple graphs whose matching polynomials

$$M(G;x) = \sum_{m\geq 0} (-1)^m \#\{\text{matchings with $m$ edges}\}\, x^{\#V(G)-2m}$$

are essentially equivalent to the Chebyshev polynomials of both kinds ($C_n$ and $P_n$ respectively), the Laguerre polynomials with integer parameter ($K_{m,n}$), and the Hermite polynomials ($K_n$).

On the other hand, my literature searches don't seem to get any results for graphs closely related to the Legendre polynomials in this way. I was wondering if there is a known construction, or a proof of impossibility, for a statement like: "There exists a family of graphs $G_n$ for which $M(G_n;x)=aP_n(bx)$, where $a$ and $b$ may depend on $n$ but not on $x$."

[Optimally $b$ would not depend on $n$, but at this point I would be happy either way.]

$\endgroup$
3
  • 1
    $\begingroup$ I assume the $P_n$ and the $P_n$ are not the same? $\endgroup$ Feb 21, 2017 at 21:22
  • $\begingroup$ The $P_n$ and the $P_n$ are not the same :P$_n$ (In case someone really was confused: the former $P_n$ is a path graph, the latter one is a Legendre polynomial) $\endgroup$ Feb 21, 2017 at 21:41
  • $\begingroup$ I didn't realize the first $P_n$ was a graph, despite having introduced that very graph under that very name in my class a few weeks ago. I need more sleep. $\endgroup$ Feb 22, 2017 at 0:15

1 Answer 1

6
$\begingroup$

Any family of orthogonal polynomials can be realized as the characteristic polynomials of a sequence of weighted paths, possibly with loops. If the implicit weight function is symmetric about the origin, loops are not needed. In this case the characteristic polynomial coincides with the matching polynomial. It follows that we can realize the Legendre polynomials as matching polynomials of weighted paths - with non-integer weights.

This is not a satisfying solution to your -roblem, at all, but it seems difficult to get further. The matching polynomial of a graph is monic and in many cases we can make our orthogonal polynomials monic by a rescaling. However the cofficients of the leading terms of the Legendre polynomials have complicated factorizations, and so no simple rescaling will help.

Finally, I am not aware of any literature that relates the Legendre polynomial to the matching polynomial of a graph. (For whatever this assertion is worth.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.