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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.