The degree sequence on tensor and cartesian products of graphs and their omega index

Bao-Hua Xing; Nurten Urlu Ozalan; Jia-Bao Liu; Bao-Hua Xing; Nurten Urlu Ozalan; Jia-Bao Liu

doi:10.3934/math.2023850

AIMS Mathematics

2023, Volume 8, Issue 7: 16618-16632. doi: 10.3934/math.2023850

Previous Article Next Article

Research article Special Issues

The degree sequence on tensor and cartesian products of graphs and their omega index

1.
School of Mathematics and Physics, Anqing Normal University, Anqing 246133, China
2.
Faculty of Engineering and Natural Science, KTO Karatay University, 42020, Konya, Turkey
3.
School of Mathematics and Physics, Anhui Jianzhu University, Hefei 230601, China

Received: 23 December 2022 Revised: 07 April 2023 Accepted: 18 April 2023 Published: 11 May 2023
MSC : 05C10, 05C62, 46A32

The aim of this paper is to illustrate how degree sequences may successfully be used over some graph products. Moreover, by taking into account the degree sequence, we will expose some new distinguishing results on special graph products. We will first consider the degree sequences of tensor and cartesian products of graphs and will obtain the omega invariant of them. After that we will conclude that the set of graphs forms an abelian semigroup in the case of tensor product whereas this same set is actually an abelian monoid in the case of cartesian product. As a consequence of these two operations, we also give a result on distributive law which would be important for future studies.
- degree sequence,
- omega index,
- tensor product,
- cartesian product
Citation: Bao-Hua Xing, Nurten Urlu Ozalan, Jia-Bao Liu. The degree sequence on tensor and cartesian products of graphs and their omega index[J]. AIMS Mathematics, 2023, 8(7): 16618-16632. doi: 10.3934/math.2023850

Related Papers:

Abstract

The aim of this paper is to illustrate how degree sequences may successfully be used over some graph products. Moreover, by taking into account the degree sequence, we will expose some new distinguishing results on special graph products. We will first consider the degree sequences of tensor and cartesian products of graphs and will obtain the omega invariant of them. After that we will conclude that the set of graphs forms an abelian semigroup in the case of tensor product whereas this same set is actually an abelian monoid in the case of cartesian product. As a consequence of these two operations, we also give a result on distributive law which would be important for future studies.

References

[1]	M. Ascioglu, M. Demirci, I. N. Cangul, Omega invariant of union, join and corona product of two graphs, Adv. Stud. Contemp. Math., 30 (2020), 297–306.
[2]	B. Basavanagoud, V. R. Desai, K. G. Mirajkar, B. Pooja, I. N. Cangul, Four new tensor products of graphs and their zagreb indices and coindices, Electron. J. Math. Anal. Appl., 8 (2020), 209–219.
[3]	W. S. Chiue, B. S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. Comput., 102 (1999), 129–137. https://doi.org/10.1016/S0096-3003(98)10041-3 doi: 10.1016/S0096-3003(98)10041-3
[4]	S. Delen, I. N. Cangul, A new graph invariant, Turk. J. Anal. Number Theory, 6 (2018), 30–33.
[5]	S. Delen, M. Togan, A. Yurttas, U. Ana, I. N. Cangul, The effect of edge and vertex deletion on omega invariant, Appl. Anal. Discrete Math., 14 (2020), 685–696. https://doi.org/10.2298/AADM190219046D doi: 10.2298/AADM190219046D
[6]	S. Delen, M. Demirci, A. S. Cevik, I. N. Cangul, On omega index and average degree of graphs, J. Math., 2021 (2021), 5565146. https://doi.org/10.1155/2021/5565146 doi: 10.1155/2021/5565146
[7]	M. Demirci, S. Delen, A. S. Cevik, I. N. Cangul, Omega index of line and total graphs, J. Math., 2021 (2021), 5552202. https://doi.org/10.1155/2021/5552202 doi: 10.1155/2021/5552202
[8]	P. Erdos, T. Gallai, Graphs with vertices having prescribed degrees, Mat. Lapok, 11 (1960), 264–274.
[9]	A. Graovac, T. Pisanski, On the Wiener index of a graph, J. Math. Chem., 8 (1991), 53–62. https://doi.org/10.1007/BF01166923 doi: 10.1007/BF01166923
[10]	Y. N. Yeh, I. Gutman, On the sum of all distances in composite graphs, Discrete Math., 135 (1994), 359–365. https://doi.org/10.1016/0012-365X(93)E0092-I doi: 10.1016/0012-365X(93)E0092-I
[11]	S. Hakami, On the realizability of a set of integers as degrees of the vertices of a graph, SIAM J. Appl. Math., 10 (1962), 496–506. https://doi.org/10.1137/0110037 doi: 10.1137/0110037
[12]	R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, Boca Raton: CRC Press, 2011.
[13]	F. Harary, Graph Theory, Reading Mass: Addison-Wesley, 1969.
[14]	V. Havel, A remark on the existence of finite graph (Hungarian), Casopis Pest., Mat., 80 (1955), 477–480.
[15]	S. Klavžar, A. Rajapakse, I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math. Lett., 9 (1996), 45–49.
[16]	D. Knuth, The art of programming, ITNow, 53 (2011), 18–19.
[17]	J. B. Liu, X. F. Pan, Minimizing Kirchhoff index among graphs with a given vertex bipartiteness, Appl. Math. Comput., 291 (2016), 84–88. https://doi.org/10.1016/j.amc.2016.06.017 doi: 10.1016/j.amc.2016.06.017
[18]	J. B. Liu, C. Wang, S. Wang, B. Wei, Zagreb indices and multiplicative zagreb indices of eulerian graphs, Bull. Malays. Math. Sci. Soc., 42 (2019), 67–78. https://doi.org/10.1007/s40840-017-0463-2 doi: 10.1007/s40840-017-0463-2
[19]	J. B. Liu, T. Zhang, Y. Wang, W. Lin, The Kirchhoff index and spanning trees of Möbius/cylinder octagonal chain, Discrete Appl. Math., 307 (2022), 22–31. https://doi.org/10.1016/j.dam.2021.10.004 doi: 10.1016/j.dam.2021.10.004
[20]	V. N. Mishra, S. Delen, I. N. Cangul, Algebraic structure of graph operations in terms of degree sequences, Int. J. Anal. Appl., 16 (2018), 809–821.
[21]	S. Pirzada, An introduction to graph theory, Acta Universitatis Sapientiae, 4 (2012), 289.
[22]	G. Sabidussi, Graph multiplication, Math. Z., 72 (1959), 446–457. https://doi.org/10.1007/BF01162967 doi: 10.1007/BF01162967
[23]	E. Sampathkumar, On tensor product graphs, J. Aust. Math. Soc., 20 (1975), 268–273. https://doi.org/10.1017/S1446788700020619 doi: 10.1017/S1446788700020619
[24]	G. Sierksma, H. Hoogeveen, Seven criteria for integer sequences being graphic, J. Graph Theory, 15 (1991), 223–231. https://doi.org/10.1002/jgt.3190150209 doi: 10.1002/jgt.3190150209
[25]	A. Tripathi, S. Venugopalan, D. B. West, A short constructive proof of the Erdős-Gallai characterization of graphic lists, Discrete Math., 310 (2010), 843–844.
[26]	S. Oğuz Ünal, Sombor Index over the Tensor and Cartesian Products of Monogenic Semigroup Graphs, Symmetry, 14 (2022), 1071.
[27]	V. G. Vizing, The Cartesian product of graphs, Vycisl. Sistemy, 9 (1963), 33.
[28]	Z. YARAHMADI, Computing some topological indices of tensor product of graphs, Iran. J. Math. Chem., 2 (2011), 109–118.
[29]	P. M. Weichsel, The Kronecker product of graphs, Proc. Am. Math. Soc., 13 (1962), 47–52.

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)