20883 research outputs found
Sort by
Premer komplementa potenčnega grafa končne grupe
No full textWe determine the diameter of every connected component of the complement of the power graph and the enhanced power graph of a finite group, which completely answers two questions by Peter J. Cameron.Določimo premer vsake povezane komponente komplementa potenčnega grafa in okrepljenega potencnega grafa končne grupe, s čimer v celoti odgovorimo na dve vprašanji Petra J. Camerona
Določitvena igra popolne prevlade
No full textA vertex u in a graph G totally dominates a vertex v if u is adjacent to v in G. A total dominating set of G is a set S of vertices of G such that every vertex of G is totally dominated by a vertex in S. The indicated total domination game is played on a graph G by two players, Dominator and Staller, who take turns making a move. In each of his moves, Dominator indicates a vertex v of the graph that has not been totally dominated in the previous moves, and Staller chooses (or selects) any vertex adjacent to v that has not yet been played, and adds it to a set D that is being built during the game. The game ends when every vertex is totally dominated, that is, when D is a total dominating set of G. The goal of Dominator is to minimize the size of D, while Staller wants just the opposite. Providing that both players are playing optimally with respect to their goals, the size of the resulting set D is the indicated total domination number of G, denoted by γti(G). In this paper we present several results on indicated total domination game. Among other results we prove that the indicated total domination number of a graph is bounded below by the well studied upper total domination number
Zgornja vložljivost grafov in produkti transpozicij, pridruženih povezavam
No full textGiven a graph, we associate each edge with the transposition which exchanges the endvertices. Fixing a linear order on the edge set, we obtain a permutation of the vertices. Dénes proved that the permutation is a full cyclic permutation for any linear order if and only if the graph is a tree.
In this article, we characterize graphs having a linear order such that the associated permutation is a full cyclic permutation in terms of graph embeddings. Moreover, we give a counter example for Eden\u27s question about an edge ordering whose associated permutation is the identity
Dominacijsko in neodvisno dominacijsko število nekaterih družin snarkov
No full textA dominating set of a graph G is a set S ⊆ V (G) such that every vertex in V (G) either belongs to S or is adjacent to some vertex in S. The domination number is the minimum cardinality of a dominating set of G. An independent dominating set of G is a dominating set that is also independent. The minimum cardinality of an independent dominating set of G is the independent domination number of G. Given the computational complexity of these problems, extensive research has been done on finding bounds or determining these parameters for classes of graphs, especially cubic graphs. Furthermore, determining how far apart these parameters are is also a challenging problem. In this work, we establish some bounds for the domination number and the independent domination number for families of cubic graphs, in particular for Generalized Blanuša Snarks and for two families of
Loupekine Snarks known as LP_0-snarks and LP_1-snarks. We also show that the parameters are equal for these graphs and conjecture that this equality holds for every snark
Neodvisnostni polinom dreves ni vedno logaritemsko konkaven, začenši z redom 26
No full textAn independent set in a graph is a collection of vertices that are not adjacent to each other. The cardinality of the largest independent set in G is represented by α(G). The independence polynomial of a graph G = (V, E) was introduced by Gutman and Harary in 1983 and is defined as
I(G x) = Σ_{k = 0}^α(G) s_k x^k = s₀ + s₁x + s₂x² + ... + s_α(G)x^α(G), where sk represents the number of independent sets in G of size k.
The problem raised by Alavi, Malde, Schwenk, and Erdös in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this problem could be strengthened up to its corresponding log-concave version. However, in 2023, this conjecture was shown to be false by Kadrawi, Levit, Yosef, and Mizrachi. In this paper, we provide further evidence against this conjecture by presenting infinite families of trees with independence polynomials that are not log-concave
