456 KB50 KB200820252025Bašić, NinoKnor, MartinŠkrekovski, Risteštevilka:2, article p2.0120 str.letnik:25DOI:10.26493/1855-3974.3085.3eaISSN:1855-3966COBISSID_HOST:232776195URN:URN:NBN:SI:doc-5PQXBDBRenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaCayley graphcubic graphsregular graphsŠoltés problemŠoltés vertexWiener indexOn regular graphs with Šoltés vertices|Let ?$W(G)$? be the Wiener index of a graph ?$G$?. We say that a vertex ?$v \in V(G)$? is a Šoltés vertex in ?$G$? if ?$W(G - v) = W(G)$?, i.e. the Wiener index does not change if the vertex ?$v$? is removed. In 1991, Šoltés posed the problem of identifying all connected graphs ?$G$? with the property that all vertices of ?$G$? are Šoltés vertices. The only such graph known to this day is ?$C_{11}$?. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least ?$k$? Šoltés vertices; or one may look for ?$\alpha$?-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least ?$\alpha$?. Note that the original problem is, in fact, to find all ?$1$?-Šoltés graphs. We intuitively believe that every ?$1$?-Šoltés graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more Šoltés vertices. In this paper, we present several partial results. For every ?$r\ge 1$? we describe a construction of an infinite family of cubic ?$2$?-connected graphs with at least ?$2^r$? Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any ?$1$?-Šoltés graph. We are only able to provide examples of large ?$\frac{1}{3}$?-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no ?$1$?-Šoltés graph other than ?$C_{11}$? existsTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije