Baskınlık Sayısı 2 ve 3 Olan İki Parçalı Graflar Üzerine Bir Not

Yıl 2021, Sayı: 28, 1071 - 1076, 30.11.2021

Havva Kırgız , Ayşe Dilek Maden

https://doi.org/10.31590/ejosat.1012651

Öz

Bağlantılı bir G grafının tüm kenarları birim direnç ile değiştirildiğinde, direnç mesafesi G ’nin herhangi iki köşesi arasındaki efektif direnç olarak hesaplanır. ’nin Kirchhoff indeksi tüm köşe çiftlerinin direnç mesafelerinin toplamı olarak tanımlanır. , G ’nin köşelerinin kümesi, ise ile köşeleri arasındaki direnç mesafesi ve , de sırasıyla ve köşelerinin eksantriği olmak üzere, bağlantılı bir grafının çarpımsal eksantrik direnç mesafası (ÇEDM) olarak tanımlanır. G grafının ÇEDM’i Kirchhoff indeksini kullanarak hesaplanabilir. Bu makalede, baskınlık sayısı 2 olan iki parçalı graflardan en küçük ve en büyük ÇEDM’e sahip olanlar karakterize edilmiştir. Ayrıca baskınlık sayısı 3 olan iki parçalı graflardan en küçük ÇEDM’e sahip olanlar karakterize edilmiştir

Anahtar Kelimeler

Elektik devreleri, Kirchhoff indeks, İki parçalı graflar, Direnç mesafesi

A Note On Bipartite Graphs with Domination Number 2 and 3

Öz

When each edge of a connected G graph is replaced by a unit resistor, the resistance distance is computed as the effective resistance between any two vertices in G. The Kirchhoff index of G is given by the sum of resistance distances between all pairs of vertices. The multiplicative eccentricity resistance-distance (MERD) of a connected graph G is defined as , where is the set of vertices of , is the resistance-distance between the vertices and , and are the eccentricity of the vertices and , respectively. The MERD of the G can be obtained by using Kirchhoff index. In this paper, we characterize the bipartite graphs which have the smallest and largest MERD with domination number 2 are given. We also characterize the bipartite graphs which have the smallest MERD with the domination number 3.

Anahtar Kelimeler

Electric circuits, Kirchhoff index, Bipartite graphs, Resistance-distance

Kaynakça

• S. Artmann, and A. Pruchnewski, “Constructing a Dominating Set for bipartite graphs in several Rounds”, Techn. Univ., Inst. für Mathematik, 2009.
• S. Artmann and J. Harant, “Random procedures for dominating sets in bipartite graphs”, Discussiones Mathematicae Graph Theory, vol. 30, pp. 277−288, 2010.
• D. Bonchev, A.T. Balaban, X. Liu, D. J. Klein, “Molecular cyclicity and centricityof polycyclic graphs I. Cyclicity based on resistance distances or reciprocal distances”, Int. J. Quantum Chem. vol. 50, pp. 1-20, 1994.
• T. Gerlach and J. Harant, "A note on domination in bipartite graphs", Discussiones Mathematicae Graph Theory vol. 22, pp.229-231, 2002.
• J. Harant and D. Rautenbach. "Domination in bipartite graphs." Discrete mathematics vol. 309, pp. 113-122, 2009.
• J. Harant and A. Pruchnewski, "A note on the domination number of a bipartite graph", Annals of Combinatorics vol. 5, pp.175-178, 2001.
• M. A. Henning, I. Schiermeyer and A. Yeo, "A new bound on the domination number of graphs with minimum degree two", the electronic journal of combinatorics pp.12-12, 2011.
• Y. Hong, Z. Zhu, A. Luo, “Some transformations on multiplicative eccentricity resistance-distance and their applications”, Appl. Math. Comput. vol. 323, pp. 75-85, 2018.
• Y. Hong, Z. Zhu, A. Luo, “Extremal graphs with diameter 2 for two indices on resistance-distance”, Discrete Math. vol. 342, pp. 487-497, 2019.
• X. J. Jiang, W. H. He, Q. Liu, J. P. Li, “On the Kirchhoff index of bipartite graphs with given diameters”, Discrete Appl. Math. vol. 283, pp. 512-521, 2020.
• D. J. Klein, M. Randic, “Resistance distance”, J. Math. Chem. vol. 12, pp. 81-95, 1993.
• N. J. Rad, "New Probabilistic Upper Bounds on the Domination Number of a Graph", The Electronic Journal of Combinatorics pp.3-28, 2019.
• L. Ye, W. Yan, “Resistance between two vertices of almost complete bipartite graphs”, Discrete Applied Mathematics, vol. 257, pp. 299-305.
• H. M. Xing, L. Sun, X. G. Chen, "An upper bound for domination number of 5-regular graphs", Czechoslovak Mathematical Journal vol. 56, pp. 1049-1061, 2006.