Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
degree polynomial; degree polynomial sequence; degree sequence; graph operation
degree polynomial; degree polynomial sequence; degree sequence; graph operation
Summary:
We introduce a new concept namely the degree polynomial for the vertices of a simple graph. This notion leads to a concept, namely, the degree polynomial sequence which is stronger than the concept of degree sequence. After obtaining the degree polynomial sequence for some well-known graphs, we prove a theorem which gives a necessary condition for the realizability of a sequence of polynomials with positive integer coefficients. Also we calculate the degree polynomial for the vertices of the join, Cartesian product, tensor product, and lexicographic product of two simple graphs and for the vertices of the complement of a simple graph. Some examples, counterexamples, and open problems concerning these subjects is given as well.
References:
[1] Aigner M., Triesch E.: Realizability and uniqueness in graphs. Discrete Math. 136 (1994), no. 1–3, 3–20. DOI 10.1016/0012-365X(94)00104-Q | MR 1313278
[2] Barrus M. D., Donovan E. A.: Neighborhood degree lists of graphs. Discrete Math. 341 (2018), no. 1, 175–183. DOI 10.1016/j.disc.2017.08.027 | MR 3713397
[3] Bertram E. A.: Some applications of graph theory to finite groups. Discrete Math. 44 (1983), no. 1, 31–43. DOI 10.1016/0012-365X(83)90004-3 | MR 0687893
[4] Bondy J. A., Murty U. S. R.: Graph Theory with Applications. American Elsevier Publishing Co., New York, 1976. MR 0411988
[5] DuBois T., Eubank S., Srinivasan A.: The effect of random edge removal on network degree sequence. Electron. J. Combin. 19 (2012), no.1, #P51, 20 pages. DOI 10.37236/2093 | MR 2900426
[6] Erdös P., Gallai T.: Graphs with prescribed degree of vertices. Mat. Lapok 11 (1960), 264–274 (Hungarian). MR 0123538
[7] Hakimi S. L.: On realizability of a set of integers as degrees of the vertices of a linear graph. J. Soc. Indust. Appl. Math. 10 (1962), no. 3, 496–506. DOI 10.1137/0110037 | MR 0148049
[8] Havel V.: A remark on the existence of finite graphs. Časopis Pěst. Mat. 80 (1955), 477---480 (Czech. Russian, German summary). DOI 10.21136/CPM.1955.108220 | MR 0089420
[9] Patrinos A. N., Hakimi S. L.: Relations between graphs and integer-pair sequences. Discrete Math. 15 (1976), no. 4, 347–358. DOI 10.1016/0012-365X(76)90048-0 | MR 0414445
[10] Ritchie M., Berthouse L., Kiss I. Z.: Generation and analysis of networks with a prescribed degree sequence and subgraph family: higher-order structure matters. J. Complex Netw. 5 (2017), no. 1, 1–31. MR 3614914
[11] Tripathi A., Tyagi H.: A simple criterion on degree sequence of graphs. Discrete Appl. Math. 156 (2008), no. 18, 3513–3517. DOI 10.1016/j.dam.2008.03.033 | MR 2467963
[12] Zverovich I. È., Zverovich V. È.: Contribution to the theory of graphic sequences. Discrete Math. 105 (1992), no. 1–3, 293–303. DOI 10.1016/0012-365X(92)90152-6 | MR 1180213
Search
Partner of
