1. Colouring a graph with position setsUllas Chandran S.V., Gabriele Di Stefano, Haritha S., Elias John Thomas, James Tuite, 2026, original scientific article Abstract: In this paper we consider a colouring version of the general position problem. The gp-chromatic number is the smallest number of colours needed to colour V(G) such that each colour class has the no-three-in-line property. We determine bounds on this colouring number in terms of the diameter, general position number, size, chromatic number, cochromatic number and total domination number and prove realisation results. We also determine it for several graph classes, including Kneser graphs K(n,2), line graphs of complete graphs, complete multipartite graphs, block graphs and Cartesian products. We also show that the gp-colouring problem is NP-complete.
Keywords: general position set, monophonic position set, graph colouring, Cartesian product, complexity
Published in RUP: 28.09.2026; Views: 188; Downloads: 2
 Full text (486,44 KB) |
2. Domination in cylindrical graphsJosé Antonio Martínez, Mercè Mora, María Luz Puertas, Javier Tejel, 2026, original scientific article Abstract: The domination number γ(Cm □ Pn) of the Cartesian product Cm □ Pn of a cycle and a path has been computed when m ≡ 0, 2 (mod 5). In the remaining cases m ≡ 1, 3, 4 (mod 5), exact formulae for γ(Cm □ Pn) have been determined when either n ≤ 22 or m ≤ 30. For the rest of the cases, only lower and upper bounds for γ(Cm □ Pn) are known. In this paper, we study γ(Cm □ Pn) when m ≡ 1, 3, 4 (mod 5). In particular, we compute γ(Cm □ Pn) if 30 ≤ m ≡ 1 (mod 5) and n ≥ 22, and we provide tighter lower and upper bounds for γ(Cm □ Pn) if m ≡ 3, 4 (mod 5).
Keywords: Domination in graphs, Cartesian product graphs, tropical matrix multiplication
Published in RUP: 20.08.2026; Views: 410; Downloads: 12
Full text (1,43 MB) |
3. In-domatic number and some operations in digraphsGermán Benítez-Bobadilla, Laura Pastrana-Ramírez, 2026, original scientific article Abstract: Let D be a digraph, a subset S of V(D) is called in-dominating set in D if for each vertex x ∈ V(D) \ S there is a vertex w ∈ S such that (x, w) ∈ A(D). An in-domatic partition of D is a partition of V(D) where all parts are in-dominating sets in D. The maximum number of parts of an in-domatic partition of D is the in-domatic number of D and it is denoted by d⁻(D). In this work, the in-domatic number for some families of digraphs such as complete digraphs, transitive digraphs, directed cycles and the cartesian product of two cycles, is calculated. Also, in-domatically critical digraphs are characterized. Additionally, the in-domatic partitions of the line digraph and some other operations which reflect the adjacency and incidence relations in digraphs are explored.
Keywords: in-domatic number, in-domatically critical digraph, line digraph, in-domatically full digraph, cartesian product
Published in RUP: 21.12.2025; Views: 1110; Downloads: 11
Full text (420,14 KB) |
4. The 2-rainbow domination number of Cartesian product of cyclesSimon Brezovnik, Darja Rupnik Poklukar, Janez Žerovnik, 2025, original scientific article Abstract: A k-rainbow dominating function (kRDF) of G is a function that assigns subsets of {1, 2, ..., k} to the vertices of G such that for vertices v with f(v) = ∅ we have
⋃{u ∈ N(v)}f(u) = {1, 2, ..., k}. The weight w(f) of a kRDF f is defined as
w(f) = ∑{v ∈ V(G)}|f(v)|. The minimum weight of a kRDF of G is called the k-rainbow domination number of G, which is denoted by γrk(G). In this paper, we study the 2-rainbow domination number of the Cartesian product of two cycles. Exact values are given for a number of infinite families and we prove lower and upper bounds for all other cases.
Keywords: 2-rainbow domination, domination number, Cartesian product
Published in RUP: 21.10.2025; Views: 1286; Downloads: 17
Full text (392,01 KB) |
5. Vertex-transitive graphs and their arc-typesMarston D. E. Conder, Tomaž Pisanski, Arjana Žitnik, 2017, original scientific article Abstract: 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.
Keywords: symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, cartesian product, covering graph
Published in RUP: 03.01.2022; Views: 4230; Downloads: 36
Full text (475,17 KB) |
6. |
7. |
8. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doctoral dissertation Keywords: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Published in RUP: 09.11.2017; Views: 7050; Downloads: 74
Full text (970,91 KB) |
9. A rhizome as a map of a rupture of the cartesian dualismKatja Cergolj Edwards, 2008, original scientific article Abstract: This essay explores the potentiality of organizing the immediate reality of lived experience of modern individual through a construct of Deleuze' and Guattari's rhizome. This practice, claimed in this essay, negates the traditional construction of knowledge, based on Cartesian perspectivalism, and offers nomadic identities of postcolonial world prospective of active, performative construction of personal bricolages
Keywords: postcolonialism, dualism, identity, cartesian, rhizome, re-presentation, multiplicity, nomadism, performativity
Published in RUP: 10.07.2015; Views: 4620; Downloads: 37
 Link to full text |
10. |
