What are Clique Polynomials? [Graph Theory Tutorial]
What are clique polynomials? This video introduces you to clique polynomials and covers their interesting properties. It shows you how to find the clique polynomial of a graph through examples.
Clique polynomials are built from the number of cliques in an undirected simple graph. The clique polynomial of an undirected graph G is defined as (c_0) + (c_1)x^1 + (c_2)x^2 + ... + (c_n)x^n, where c_i is the number of i-cliques in G. Note that c_0, or the number of 0 cliques, is always 1 for any graph, and that this polynomial terminates with the term corresponding to the largest clique(s) in the graph, an n-clique. To find the clique polynomial of a graph, you would first count the number of cliques of each size in the graph and then apply each as the coefficient of the term with the same degree as the size of that clique. Different (non-isomorphic) graphs can have the same clique polynomial, but isomorphic graphs always have the same clique polynomial. Also, we can find the clique polynomial of certain graph products based off the clique polynomials of the factor graphs. Finally, there are several ways to tell whether a polynomial could be a clique polynomial of some graph or not, and we'll cover them in this video.
See these links for more info:
https://citeseerx.ist.psu.edu/viewdoc...
https://arxiv.org/abs/1910.11196
https://mathworld.wolfram.com/CliqueP...
Thanks for watching!
Watch video What are Clique Polynomials? [Graph Theory Tutorial] online without registration, duration hours minute second in high quality. This video was added by user Vital Sine 17 May 2021, don't forget to share it with your friends and acquaintances, it has been viewed on our site 1,093 once and liked it 28 people.