×

Proofs of the AutoGraphiX conjectures on the domination number, average eccentricity and proximity. (English) Zbl 1454.05092

Summary: The eccentricity of a vertex is the greatest distance from it to any other vertex and the average eccentricity of a graph \(G\) is the average value of eccentricities of all vertices of \(G\). The proximity of a vertex in a connected graph is the average distance from it to all other vertices and the proximity of a connected graph \(G\) is the minimum average distance from a vertex of \(G\) to all others. A set \(S \subseteq V ( G )\) is called a dominating set of \(G\) if \(N_G ( x ) \bigcap S \neq \emptyset\) for any vertex \(x \in V ( G ) \setminus S\). The domination number \(\gamma ( G )\) of \(G\) is the minimum cardinality of all dominating sets of \(G\). In this paper, we improve and prove two AutoGraphiX conjectures. One gives the sharp upper bound on the quotient of the domination number and average eccentricity, and another shows the sharp upper bound about the difference between the domination number and proximity.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C12 Distance in graphs
05C40 Connectivity

Software:

AutoGraphiX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aouchiche, M., Comparaison automatisée d’invariants en théorie des graphes (2006), École Polytechnique de Montréal, February
[2] Aouchiche, M.; Bonnefoy, J. M.; Fidahoussen, A.; Caporossi, G.; Hansen, P.; Hiesse, L.; Lacheré, J.; Monhait, A., Variable neighborhood search for extremal graphs, 14. The AutoGraphiX 2 System, (Liberti, L.; Maculan, N., Global Optimization: From Theory to Implementation (2006), Springer), 281-310 · Zbl 1100.90052
[3] Aouchiche, M.; Brinkmann, G.; Hansen, P., Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number, Discrete Appl. Math., 156, 2530-2542 (2008) · Zbl 1173.05022
[4] Aouchiche, M.; Hansen, P., Automated results and conjectures on average distance in graphs, (Graph Theory in Paris. Graph Theory in Paris, Trends Math., vol. VI (2007)), 21-36 · Zbl 1114.05050
[5] Aouchiche, M.; Hansen, P., Nordhaus-Gaddum relations for proximity and remoteness in graphs, Comput. Math. Appl., 59, 2827-2835 (2010) · Zbl 1193.05092
[6] Aouchiche, M.; Hansen, P., A survey of automated conjectures in spectral graph theory, Linear Algebra Appl., 432, 2293-2322 (2010) · Zbl 1218.05087
[7] Aouchiche, M.; Hansen, P., Distance Laplacian eigenvalues and chromatic number in graphs, Filomat, 31, 2545-2555 (2017) · Zbl 1488.05291
[8] Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs. I. the AutoGraphiX system, Discrete Math., 212, 29-44 (2000) · Zbl 0947.90130
[9] Cockayne, E. J.; Hedetniemi, S. T.; Miller, D. J., Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 21, 461-468 (1978) · Zbl 0393.05044
[10] Du, Z. B.; Ilić, A., On AGX conjectures regarding average eccentricity, MATCH Commun. Math. Comput. Chem., 69, 597-609 (2013) · Zbl 1299.05082
[11] Du, Z. B.; Ilić, A., A proof of the conjecture regarding the sum of domination number and average eccentricity, Discrete Appl. Math., 201, 105-113 (2016) · Zbl 1329.05229
[12] Hua, H. B.; Wang, H. Z.; Hu, X. L., On eccentric distance sum and degree distance of graphs, Discrete Appl. Math., 250, 262-275 (2018) · Zbl 1398.05075
[13] Ilić, A., On the extremal properties of the average eccentricity, Comput. Math. Appl., 64, 2877-2885 (2012) · Zbl 1268.05057
[14] Liang, M. L.; Liu, B. L., A proof of two conjectures on the Randić index and the average eccentricity, Discrete Math., 312, 2446-2449 (2012) · Zbl 1246.05041
[15] Liang, M. L.; Liu, J. X., Proofs of conjectures on the Randić index and average eccentricity, Discrete Appl. Math., 202, 188-193 (2016) · Zbl 1330.05045
[16] Ma, B.; Wu, B.; Zhang, W., Proximity and average eccentricity of a graph, Inform. Process. Lett., 112, 392-395 (2012) · Zbl 1243.05073
[17] McCuaig, W.; Shepherd, B., Domination in graphs with minimum degree two, J. Graph Theory, 13, 749-762 (1989) · Zbl 0708.05058
[18] O. Ore, Theory of Graphs, American Mathematical Society Colloquium, Publication Vol. 38, Providence, RI, 1962. · Zbl 0105.35401
[19] Payan, C.; Xuong, N. H., Domination-balanced graphs, J. Graph Theory, 6, 23-32 (1982) · Zbl 0489.05049
[20] Pei, L. D.; Pan, X. F., Extremal values on Zagreb indices of trees with given distance \(k\)-domination number, J. Inequal. Appl., 16 (2018) · Zbl 1378.05102
[21] Pei, L. D.; Pan, X. F., The minimum eccentric distance sum of trees with given distance \(k\)-domination number, Discrete Math. Algorithms Appl., 12, 16 (2020) · Zbl 1457.05055
[22] Pei, L. D.; Pan, X. F.; Hu, F. T., Some improved inequalities related to Vizing’s conjecture, Inform. Process. Lett., 135, 85-91 (2018) · Zbl 1476.05159
[23] Pei, L. D.; Pan, X. F.; Tian, J.; Peng, G. Q., On AutoGraphiX conjecture regarding domination number and average eccentricity, Filomat, 3, 699-710 (2019) · Zbl 1499.05196
[24] Reed, B., Paths, stars and the number three, Combin. Probab. Comput., 5, 277-295 (1996) · Zbl 0857.05052
[25] Sedlar, J.; Vukičević, D.; Aouchiche, M.; Hansen, P., Variable neighborhood search for extremal graphs. 25. Products of connectivity and distance measures, Graph Theory Notes N. Y., 156, 2530-2542 (2008) · Zbl 1173.05022
[26] Stevanović, D., Resolution of AutoGraphiX conjectures relating the index and matching number of graphs, Linear Algebra Appl., 433, 1674-1677 (2010) · Zbl 1211.05078
[27] Xu, B. G.; Cockayne, E. J.; Haynes, T. W.; Hedetniemi, S. T.; Zhou, S. C., Extremal graphs for inequalities involving domination parameters, Discrete Math., 216, 1-10 (2000) · Zbl 0954.05037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.