Degree polynomial for vertices in a graph and its behavior under graph operations

Reza Jafarpour-Golzari

Commentationes Mathematicae Universitatis Carolinae (2022)

  • Volume: 62 63, Issue: 4, page 397-413
  • ISSN: 0010-2628

Abstract

top
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.

How to cite

top

Jafarpour-Golzari, Reza. "Degree polynomial for vertices in a graph and its behavior under graph operations." Commentationes Mathematicae Universitatis Carolinae 62 63.4 (2022): 397-413. <http://eudml.org/doc/299038>.

@article{Jafarpour2022,
abstract = {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.},
author = {Jafarpour-Golzari, Reza},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {degree polynomial; degree polynomial sequence; degree sequence; graph operation},
language = {eng},
number = {4},
pages = {397-413},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Degree polynomial for vertices in a graph and its behavior under graph operations},
url = {http://eudml.org/doc/299038},
volume = {62 63},
year = {2022},
}

TY - JOUR
AU - Jafarpour-Golzari, Reza
TI - Degree polynomial for vertices in a graph and its behavior under graph operations
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2022
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 62 63
IS - 4
SP - 397
EP - 413
AB - 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.
LA - eng
KW - degree polynomial; degree polynomial sequence; degree sequence; graph operation
UR - http://eudml.org/doc/299038
ER -

References

top
  1. Aigner M., Triesch E., 10.1016/0012-365X(94)00104-Q, Discrete Math. 136 (1994), no. 1–3, 3–20. MR1313278DOI10.1016/0012-365X(94)00104-Q
  2. Barrus M. D., Donovan E. A., 10.1016/j.disc.2017.08.027, Discrete Math. 341 (2018), no. 1, 175–183. MR3713397DOI10.1016/j.disc.2017.08.027
  3. Bertram E. A., 10.1016/0012-365X(83)90004-3, Discrete Math. 44 (1983), no. 1, 31–43. MR0687893DOI10.1016/0012-365X(83)90004-3
  4. Bondy J. A., Murty U. S. R., Graph Theory with Applications, American Elsevier Publishing Co., New York, 1976. MR0411988
  5. DuBois T., Eubank S., Srinivasan A., 10.37236/2093, Electron. J. Combin. 19 (2012), no.1, #P51, 20 pages. MR2900426DOI10.37236/2093
  6. Erdös P., Gallai T., Graphs with prescribed degree of vertices, Mat. Lapok 11 (1960), 264–274 (Hungarian). MR0123538
  7. Hakimi S. L., 10.1137/0110037, J. Soc. Indust. Appl. Math. 10 (1962), no. 3, 496–506. MR0148049DOI10.1137/0110037
  8. Havel V., 10.21136/CPM.1955.108220, Časopis Pěst. Mat. 80 (1955), 477---480 (Czech. Russian, German summary). MR0089420DOI10.21136/CPM.1955.108220
  9. Patrinos A. N., Hakimi S. L., 10.1016/0012-365X(76)90048-0, Discrete Math. 15 (1976), no. 4, 347–358. MR0414445DOI10.1016/0012-365X(76)90048-0
  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. MR3614914
  11. Tripathi A., Tyagi H., 10.1016/j.dam.2008.03.033, Discrete Appl. Math. 156 (2008), no. 18, 3513–3517. MR2467963DOI10.1016/j.dam.2008.03.033
  12. Zverovich I. È., Zverovich V. È., 10.1016/0012-365X(92)90152-6, Discrete Math. 105 (1992), no. 1–3, 293–303. MR1180213DOI10.1016/0012-365X(92)90152-6

NotesEmbed ?

top

You must be logged in to post comments.