1. Nut digraphsNino Bašić, Patrick W. Fowler, Maxine M. McCarthy, Primož Potočnik, 2026, izvirni znanstveni članek Opis: A nut graph is a simple graph whose kernel is spanned by a single full vector (i.e., the adjacency matrix has a single zero eigenvalue and all non-zero kernel eigenvectors have no zero entry). We classify generalisations of nut graphs to nut digraphs: a digraph whose kernel (resp. co-kernel) is spanned by a full vector is dextro-nut (resp. laevo-nut); a bi-nut digraph is both laevo- and dextro-nut; an ambi-nut digraph is a bi-nut digraph where kernel and co-kernel are spanned by the same vector; a digraph is inter-nut if the intersection of the kernel and co-kernel is spanned by a full vector. It is known that a nut graph is connected, leafless and non-bipartite. It is shown here that an ambi-nut digraph is strongly connected, non-bipartite (i.e., has a non-bipartite underlying graph) and has minimum in-degree and minimum out-degree of at least 2. Refined notions of core and core-forbidden vertices apply to singular digraphs. Infinite families of nut digraphs and systematic coalescence, crossover and multiplier constructions are introduced. Relevance of nut digraphs to topological physics is discussed.
Ključne besede: nut graph, core graph, nullity, directed graph, nut digraph, dextro-nut, laevo-nut, bi-nut, ambi-nut, inter-nut, dextro-core vertex, laevo-core vertex, graph spectra
Objavljeno v RUP: 09.01.2026; Ogledov: 193; Prenosov: 8
 Celotno besedilo (873,25 KB)
Gradivo ima več datotek! Več... |
2. Nut graphs with a prescribed number of vertex and edge orbitsNino Bašić, Ivan Damnjanović, 2026, izvirni znanstveni članek Opis: A nut graph is a nontrivial graph whose adjacency matrix has a one-dimensional null space spanned by a vector without zero entries. Recently, it was shown that a nut graph has more edge orbits than vertex orbits. It was also shown that for any even $r \geq 2$ and any $k \geq r + 1$, there exist infinitely many nut graphs with r vertex orbits and k edge orbits. Here, we extend this result by finding all the pairs $(r, k)$ for which there exists a nut graph with $r$ vertex orbits and $k$ edge orbits. In particular, we show that for any $k \geq 2$, there are infinitely many Cayley nut graphs with $k$ edge orbits and $k$ arc orbits.
Ključne besede: nut graph, vertex orbit, edge orbit, arc orbit, Cayley graph, automorphism
Objavljeno v RUP: 09.01.2026; Ogledov: 222; Prenosov: 5
Celotno besedilo (445,35 KB)
Gradivo ima več datotek! Več... |
3. Adjacent vertex distinguishing total coloring of corona product of graphsHanna Furmańczyk, Rita Zuazua, 2025, izvirni znanstveni članek Opis: An adjacent vertex distinguishing total k-coloring f of a graph G is a proper total k-coloring of G such that no pair of adjacent vertices has the same color sets, where the color set at a vertex v, C_f^G(v), is {f(v)} ∪ {f(vu)|u ∈ V(G), vu ∈ E(G)}. In 2005 Zhang et al. posted the conjecture (AVDTCC) that every simple graph G has adjacent vertex distinguishing total (Δ(G) + 3)-coloring. In this paper we confirm the conjecture for many types of coronas, in particular for generalized, simple and l-coronas of graphs, not relating the results to particular graph classes of the factors.
Ključne besede: corona graph, l-corona, generalized corona graph, adjacent vertex distinguishing total coloring, AVDTC Conjecture
Objavljeno v RUP: 21.10.2025; Ogledov: 322; Prenosov: 1
Celotno besedilo (367,69 KB) |
4. Basic tetravalent oriented graphs of independent-cycle typeNemanja Poznanović, Cheryl E. Praeger, 2025, izvirni znanstveni članek Opis: The family OG(4) consisting of graph-group pairs (Γ, G), where Γ is a finite, connected, 4-valent graph admitting a G-vertex-, and G-edge-transitive, but not G-arc-transitive action, has recently been examined using a normal quotient methodology. A subfamily of OG(4) has been identified as ‘basic’, due to the fact that all members of OG(4) are normal covers of at least one basic pair. We provide an explicit classification of those basic pairs (Γ, G) which have at least two independent cyclic G-normal quotients (these are G-normal quotients which are not extendable to a common cyclic normal quotient).
Ključne besede: half-arc-transitive, vertex-transitive graph, edge-transitive graph, normal cover, cycle graph
Objavljeno v RUP: 21.10.2025; Ogledov: 389; Prenosov: 1
Celotno besedilo (398,19 KB) |
5. On regular graphs with Šoltés verticesNino Bašić, Martin Knor, Riste Škrekovski, 2025, izvirni znanstveni članek Opis: 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}$▫ exists.
Ključne besede: Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex
Objavljeno v RUP: 10.09.2025; Ogledov: 407; Prenosov: 2
Celotno besedilo (456,75 KB) |
6. |
7. The core of a vertex-transitive complementary prismMarko Orel, 2023, izvirni znanstveni članek Opis: The complementary prism ▫$\Gamma \overline{\Gamma}$▫ is obtained from the union of a graph ▫$\Gamma$▫ and its complement ▫$\overline{\Gamma}$▫ where each pair of identical vertices in ▫$\Gamma$▫ and ▫$\overline{\Gamma}$▫ is joined by an edge. It generalizes the Petersen graph, which is the complementary prism of the pentagon. The core of a vertex-transitive complementary prism is studied. In particular, it is shown that a vertex-transitive complementary prism ▫$\Gamma \overline{\Gamma}$▫ is a core, i.e. all its endomorphisms are automorphisms, whenever ▫$\Gamma$▫ is a core or its core is a complete graph.
Ključne besede: graph homomorphism, complementary prism, self-complementary graph, vertex-transitive graph, core
Objavljeno v RUP: 06.11.2023; Ogledov: 2537; Prenosov: 13
Celotno besedilo (305,54 KB) |
8. |
9. |
10. Vertex-transitive graphs and their arc-typesMarston D. E. Conder, Tomaž Pisanski, Arjana Žitnik, 2017, izvirni znanstveni članek Opis: Let ▫$X$▫ be a finite vertex-transitive graph of valency ▫$d$▫, and let ▫$A$▫ be the full automorphism group of ▫$X$▫. Then the arc-type of ▫$X$▫ is defined in terms of the sizes of the orbits of the stabiliser ▫$A_v$▫ of a given vertex ▫$v$▫ on the set of arcs incident with ▫$v$▫. Such an orbit is said to be self-paired if it is contained in an orbit ▫$\Delta$▫ of ▫$A$▫ on the set of all arcs of v$X$▫ such that v$\Delta$▫ is closed under arc-reversal. The arc-type of ▫$X$▫ is then the partition of ▫$d$▫ as the sum ▫$n_1 + n_2 + \dots + n_t + (m_1 + m_1) + (m_2 + m_2) + \dots + (m_s + m_s)$▫, where ▫$n_1, n_2, \dots, n_t$▫ are the sizes of the self-paired orbits, and ▫$m_1,m_1, m_2,m_2, \dots, m_s,m_s$▫ are the sizes of the non-self-paired orbits, in descending order. In this paper, we find the arc-types of several families of graphs. Also we show that the arc-type of a Cartesian product of two "relatively prime" graphs is the natural sum of their arc-types. Then using these observations, we show that with the exception of ▫$1+1$▫ and ▫$(1+1)$▫, every partition as defined above is \emph{realisable}, in the sense that there exists at least one vertex-transitive graph with the given partition as its arc-type.
Ključne besede: symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, cartesian product, covering graph
Objavljeno v RUP: 03.01.2022; Ogledov: 3073; Prenosov: 26
Celotno besedilo (475,17 KB) |
