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

Ö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

Abstract

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.

Keywords

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

Kaynakça

1. S. Artmann, and A. Pruchnewski, “Constructing a Dominating Set for bipartite graphs in several Rounds”, Techn. Univ., Inst. für Mathematik, 2009.
2. S. Artmann and J. Harant, “Random procedures for dominating sets in bipartite graphs”, Discussiones Mathematicae Graph Theory, vol. 30, pp. 277−288, 2010.
3. 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.
4. T. Gerlach and J. Harant, "A note on domination in bipartite graphs", Discussiones Mathematicae Graph Theory vol. 22, pp.229-231, 2002.
5. J. Harant and D. Rautenbach. "Domination in bipartite graphs." Discrete mathematics vol. 309, pp. 113-122, 2009.
6. J. Harant and A. Pruchnewski, "A note on the domination number of a bipartite graph", Annals of Combinatorics vol. 5, pp.175-178, 2001.
7. 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.
8. 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.

9. 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.
10. 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.
11. D. J. Klein, M. Randic, “Resistance distance”, J. Math. Chem. vol. 12, pp. 81-95, 1993.
12. N. J. Rad, "New Probabilistic Upper Bounds on the Domination Number of a Graph", The Electronic Journal of Combinatorics pp.3-28, 2019.
13. L. Ye, W. Yan, “Resistance between two vertices of almost complete bipartite graphs”, Discrete Applied Mathematics, vol. 257, pp. 299-305.
14. 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.