Article
| Title: | Degree polynomial for vertices in a graph and its behavior under graph operations (English) |
| Author: | Jafarpour-Golzari, Reza |
| Language: | English |
| Journal: | Commentationes Mathematicae Universitatis Carolinae |
| ISSN: | 0010-2628 (print) |
| ISSN: | 1213-7243 (online) |
| Volume: | 63 |
| Issue: | 4 |
| Year: | 2022 |
| Pages: | 397-413 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | degree polynomial |
| Keyword: | degree polynomial sequence |
| Keyword: | degree sequence |
| Keyword: | graph operation |
| MSC: | 05C07 |
| MSC: | 05C31 |
| MSC: | 05C76 |
| idZBL: | Zbl 07723830 |
| idMR: | MR4577038 |
| DOI: | 10.14712/1213-7243.2023.006 |
| . | |
| Date available: | 2023-04-20T13:45:28Z |
| Last updated: | 2023-10-27 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/151641 |
| . | |
| Reference: | [1] Aigner M., Triesch E.: Realizability and uniqueness in graphs.Discrete Math. 136 (1994), no. 1–3, 3–20. MR 1313278, 10.1016/0012-365X(94)00104-Q |
| Reference: | [2] Barrus M. D., Donovan E. A.: Neighborhood degree lists of graphs.Discrete Math. 341 (2018), no. 1, 175–183. MR 3713397, 10.1016/j.disc.2017.08.027 |
| Reference: | [3] Bertram E. A.: Some applications of graph theory to finite groups.Discrete Math. 44 (1983), no. 1, 31–43. MR 0687893, 10.1016/0012-365X(83)90004-3 |
| Reference: | [4] Bondy J. A., Murty U. S. R.: Graph Theory with Applications.American Elsevier Publishing Co., New York, 1976. MR 0411988 |
| Reference: | [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. MR 2900426, 10.37236/2093 |
| Reference: | [6] Erdös P., Gallai T.: Graphs with prescribed degree of vertices.Mat. Lapok 11 (1960), 264–274 (Hungarian). MR 0123538 |
| Reference: | [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. MR 0148049, 10.1137/0110037 |
| Reference: | [8] Havel V.: A remark on the existence of finite graphs.Časopis Pěst. Mat. 80 (1955), 477---480 (Czech. Russian, German summary). MR 0089420, 10.21136/CPM.1955.108220 |
| Reference: | [9] Patrinos A. N., Hakimi S. L.: Relations between graphs and integer-pair sequences.Discrete Math. 15 (1976), no. 4, 347–358. MR 0414445, 10.1016/0012-365X(76)90048-0 |
| Reference: | [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 |
| Reference: | [11] Tripathi A., Tyagi H.: A simple criterion on degree sequence of graphs.Discrete Appl. Math. 156 (2008), no. 18, 3513–3517. MR 2467963, 10.1016/j.dam.2008.03.033 |
| Reference: | [12] Zverovich I. È., Zverovich V. È.: Contribution to the theory of graphic sequences.Discrete Math. 105 (1992), no. 1–3, 293–303. MR 1180213, 10.1016/0012-365X(92)90152-6 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
