51. |
52. |
53. A note on Cayley nut graphs whose degree is divisible by fourIvan Damnjanović, 2026, izvirni znanstveni članek Opis: A nut graph is a nontrivial simple graph such that its adjacency matrix has a one-dimensional null space spanned by a full vector. Fowler et al. in 2020 proved that there is a d-regular vertex-transitive nut graph of order n only if 4 ∣ d, 2 ∣ n, n ≥ d + 4 or d≡₄2, 4 ∣ n and n ≥ d + 6. It was recently shown that there exists a d-regular circulant nut graph of order n if and only if 4 ∣ d, 2 ∣ n, d > 0, together with n ≥ d + 4 if d≡₈4 and n ≥ d + 6 if 8 ∣ d, as well as (n, d) ≠ (16, 8) (in the paper from 2024). In this paper, we demonstrate the existence of a d-regular Cayley nut graph of order n for each n and d with 4 ∣ d, d > 0 and 2 ∣ n, n ≥ d + 4, thereby finding all the orders attainable by a Cayley nut graph, or vertex-transitive nut graph, with a fixed degree divisible by four.
Ključne besede: nut graph, Cayley graph, vertex-transitive graph, circulant graph, graph spectrum, graph eigenvalue
Objavljeno v RUP: 23.03.2026; Ogledov: 168; Prenosov: 4
 Celotno besedilo (404,59 KB) |
54. Paint cost spectrum of perfect k-ary treesSonwabile Mafunda, Jonathan L. Merzel, Katherine E. Perry, Anna Varvak, 2026, izvirni znanstveni članek Opis: We determine the paint cost spectrum for perfect k-ary trees. A coloring of the vertices of a graph G with d colors is said to be d-distinguishing if only the trivial automorphism preserves the color classes. The smallest such d is the distinguishing number of G and is denoted Dist(G). The paint cost of d-distinguishing G, denoted ρd(G), is the minimum size of the complement of a color class over all d-distinguishing colorings. A subset S of the vertices of G is said to be a fixing set for G if the only automorphsim that fixes the vertices in S pointwise is the trivial automorphism. The cardinality of a smallest fixing set is denoted Fix(G). In this paper, we explore the breaking of symmetry in perfect k-ary trees by investigating what we define as the paint cost spectrum of a graph G: (Dist(G); ρDist(G)(G), ρDist(G)+1(G), . . . , ρFix(G)+1(G)) and the paint cost ratio of G, which is defined to be the fraction of paint costs in the paint cost spectrum equal to Fix(G). We determine both the paint cost spectrum and the paint cost ratio completely for perfect k-ary trees. We also prove a lemma that is of interest in its own right: given an n-tuple, n ≥ 2 of distinct elements of an ordered abelian group and 1 ≤ k ≤ n! − 1, there exists a k × n row permuted matrix with distinct column sums.
Ključne besede: distinguishing coloring, fixing set, symmetry, cost of distinguishing
Objavljeno v RUP: 23.03.2026; Ogledov: 173; Prenosov: 5
Celotno besedilo (441,47 KB) |
55. The Clar-Fries mysteryJoshua Fenton, Jack Edward Graver, Elizabeth J. Hartung, 2026, izvirni znanstveni članek Opis: A fullerene is a 3-regular plane graph whose faces are hexagons and pentagons. The Fries number of a fullerene is the largest number of benzene rings over all possible Kekulé structures while the Clar number of a fullerene is the largest number of independent benzene rings over all possible Kekulé structures. One question was whether it is always the case that a largest set of independent benzene rings, giving the Clar number, must be a subset of some largest set of benzene rings giving the Fries number. This question is still open for benzenoids, but was answered negatively for fullerenes, with the first counterexample given in paper from E. J. Hartung in 2014. In 2016 in paper from J. E. Graver and E. J. Hartung, the authors constructed a family of fullerenes with the property that the set of benzene rings giving the Clar number was actually disjoint from the set of benzene rings giving the Fries number. Fowler and Myrvold then developed a program for computing the Clar number directly and discovered a significant number of fullerenes in which the Clar sets were not a subset of any Fries set and most of these were not of the type constructed in paper from J. E. Graver and E. J. Hartung in 2016. Exactly why this occurs is somewhat of a mystery. In her Ph.D. thesis, Hartung developed the concept of Clar chains to describe the Kekulé structure giving the Clar sets; in his Ph.D. thesis, Fenton developed the concept of a Fries mesh to describe the Kekulé structure giving the Fries sets. Comparing these two constructions enables us to shed some light on this mystery.
Ključne besede: fullerene, Clar number, Fries number
Objavljeno v RUP: 23.03.2026; Ogledov: 143; Prenosov: 8
Celotno besedilo (1,78 MB) |
56. Complete co-secure domination in graphsGisha Saraswathy, Manju K. Menon, 2026, izvirni znanstveni članek Opis: A dominating set S ⊆ V is a co-secure dominating set if for each u ∈ S there exists v ∈ V \ S such that v is adjacent to u and (S \ {u}) ∪ {v} is a dominating set. The cardinality of a minimum co-secure dominating set in G is called the cosecure domination number of G and is denoted by γcs(G). The study of a co-secure dominating set is important in interconnection networks as it studies its security. In cosecure domination, a guard can ensure the safety of only one of its adjacent unguarded vertices. This motivated us to define a new domination parameter called complete co-secure domination, in which a guard can move to any one of its adjacent unguarded vertices without compromising the protection of G. A co-secure dominating set S is called a complete co-secure dominating set if for every u ∈ S and for every v ∈ V \ S that is adjacent to u, (S \ {u})∪ {v} is a dominating set. The cardinality of a minimum complete co-secure dominating set is called the complete co-secure domination number of G and is denoted by γccs(G). In this paper, we study the complete co-secure domination in graphs and determined the lower and upper bounds and have checked their sharpness. We have proved that for any positive integer m, there exists a graph whose co-secure domination number is m and complete co-secure domination number is b, where m ≤ b ≤ 2m. We characterize graphs G such that γcs(G) = γccs(G). We obtain a condition for which γcs(G) = γccs(G) = γs(G) for graphs with δ(G) ≥ 2, thus partially resolving a question posed in paper from Arumugam, Ebadi and Manrique from 2014. We also obtain the complete co-secure domination number of some families of graphs.
Ključne besede: domination number, co-secure domination number, complete co-secure domination number
Objavljeno v RUP: 20.03.2026; Ogledov: 210; Prenosov: 10
Celotno besedilo (437,20 KB) |
57. Nonuniform lines on finite projective planesÁdám Markó, 2026, izvirni znanstveni članek Opis: We consider the stability version of the following problem, originally posed by Erdős: colour the points of a projective plane of order q, q odd, with two colours. What is the minimum number of nonuniform lines, that is the lines on which the number of points of the two colours are not the same. It is easy to show that the number of nonuniform lines is at least q+1 and there is a trivial colouring with q+1 nonuniform lines. Our main result is that the number of nonuniform lines is at least 13/8 * q or we have the trivial colouring.
Ključne besede: colouring, projective planes, blocking sets
Objavljeno v RUP: 20.03.2026; Ogledov: 186; Prenosov: 3
Celotno besedilo (414,61 KB) |
58. |
59. |
60. |
