1. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2012, izvirni znanstveni članek Opis: Roman domination is a historically inspired variety of general domination such that every vertex is labeled with labels from $\{0,1,2\}$. Roman domination number is the smallest of the sums of labels fulfilling condition that every vertex, labeled 0, has a neighbor, labeled 2. Using algebraic approach we give ▫$O(C)$▫ time algorithm for computing Roman domination number of special classes of polygraphs (rota- and fasciagraphs). By implementing the algorithm we give formulas for Roman domination number of the Cartesian products of paths and cycles ▫$P_n \Box P_k$▫, ▫$P_n \Box C_k$▫ for ▫$k \leq 8$▫ and ▫$n \in {\mathbb N}$▫ and for ▫$C_n \Box P_k$▫ and ▫$C_n \Box C_k$▫ for ▫$k \leq 5$▫, ▫$n \in {\mathbb N}$▫. We also give a list of Roman graphs among investigated families.
Ključne besede: graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Objavljeno v DKUM: 23.08.2017; Ogledov: 1634; Prenosov: 246
 Celotno besedilo (719,06 KB)
Gradivo ima več datotek! Več... |
2. Weak k-reconstruction of Cartesian productsWilfried Imrich, Blaž Zmazek, Janez Žerovnik, 2003, izvirni znanstveni članek Opis: By Ulam's conjecture every finite graph ▫$G$▫ can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of ▫$k$▫-vertex deleted subgraphs of Cartesian products and prove that one can decide whether a graph ▫$H$▫ is a ▫$k$▫-vertex deleted subgraph of a Cartesian product ▫$G$▫ with at least ▫$k+1$▫ prime factors on at least ▫$k+1$▫ vertices each, and that ▫$H$▫ uniquely determines ▫$G$▫. This extends previous works of the authors and Sims. This paper also contains a counterexample to a conjecture of MacAvaney.
Ključne besede: mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 1558; Prenosov: 426
Celotno besedilo (197,33 KB)
Gradivo ima več datotek! Več... |
3. The periphery graph of a median graphBoštjan Brešar, Manoj Changat, Ajitha R. Subhamathi, Aleksandra Tepeh, 2010, izvirni znanstveni članek Opis: The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like median graphs with arbitrarily large geodetic number. Peripheral expansion with respect to periphery graph is also considered, and connections with the concept of crossing graph are established.
Ključne besede: mathematics, graph theory, median graph, Cartesian product, geodesic, periphery, peripheral expansion
Objavljeno v DKUM: 31.03.2017; Ogledov: 1478; Prenosov: 411
Celotno besedilo (145,86 KB)
Gradivo ima več datotek! Več... |
4. Recognizing weighted directed Cartesian graph bundlesBlaž Zmazek, Janez Žerovnik, 2000, izvirni znanstveni članek Opis: In this paper we show that methods for recognizing Cartesian graph bundles can be generalized to weighted digraphs. The main result is an algorithm which lists the sets of degenerate arcs for all representations of digraph as a weighted directed Cartesian graph bundle over simple base digraphs not containing transitive tournament on three vertices. Two main notions are used.The first one is the new relation ▫$\vec{\delta}^\ast$▫ defined among the arcs of a digraph as a weighted directed analogue of the well-known relation ▫$\delta^\ast$▫. The second one is the concept of half-convex subgraphs. A subgraph ▫$H$▫ is half-convex in ▫$G$▫ if any vertex ▫$x \in G \setminus H$▫ has at most one predecessor and at most one successor
Ključne besede: mathematics, graph theory, graph bundles, Cartesian graph product, weighted digraphs, half-convexity
Objavljeno v DKUM: 31.03.2017; Ogledov: 1303; Prenosov: 379
Celotno besedilo (240,86 KB)
Gradivo ima več datotek! Več... |
5. On Vizing's conjectureBoštjan Brešar, 2001, izvirni znanstveni članek Opis: A dominating set ▫$D$▫ gor a graph ▫$G$▫ is a subset ▫$V(G)$▫ such that any vertex in ▫$V(G)-D$▫ has a neighbor in ▫$D$▫, and a domination number ▫$\gamma(G)$▫ is the size of a minimum dominating set for ▫$G$▫. For the Cartesian product ▫$G \Box H$▫ Vizing's conjecture states that ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫ for every pair of graphs ▫$G,H$▫. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when ▫$\gamma(G) = \gamma(H) = 3$▫.
Ključne besede: mathematics, graph theory, graph, Cartesian product, domination number
Objavljeno v DKUM: 31.03.2017; Ogledov: 1520; Prenosov: 119
Celotno besedilo (126,98 KB)
Gradivo ima več datotek! Več... |
6. |
7. On [Theta]-graphs of partial cubesSandi Klavžar, Matjaž Kovše, 2007, izvirni znanstveni članek Opis: The ▫$\Theta$▫-graph ▫$\Theta(G)$▫ of a partial cube ▫$G$▫ is the intersection graph of the equivalence classes of the Djokovic-Winkler relation. ▫$\Theta$▫-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, ▫$\Theta(G)$▫ is complete if and only if ▫$G$▫ can be obtained from ▫$K_1$▫ by a sequence of (newly introduced) dense expansions. ▫$\Theta$▫-graphs are also compared with familiar concepts of crossing graphs and ▫$\tau$▫-graphs.
Ključne besede: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 1119; Prenosov: 140
Celotno besedilo (150,56 KB)
Gradivo ima več datotek! Več... |
8. Edge-transitive lexicographic and cartesian productsWilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani, 2016, izvirni znanstveni članek Opis: In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product ▫$G \circ H$▫ of a connected graph ▫$G$▫ that is not complete by a graph ▫$H$▫, we show that it is edge-transitive if and only if ▫$G$▫ is edge-transitive and ▫$H$▫ is edgeless. If the first factor of ▫$G \circ H$▫ is non-trivial and complete, then ▫$G \circ H$▫ is edge-transitive if and only if ▫$H$▫ is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao (Appl. Math. Lett. 24 (2011) 1924--1926). For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
Ključne besede: edge-transitive graph, vertex-transitive graph, lexicographic product of graphs, Cartesian product of graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 1072; Prenosov: 426
Celotno besedilo (150,33 KB)
Gradivo ima več datotek! Več... |
9. A note on the chromatic number of the square of the Cartesian product of two cyclesZehui Shao, Aleksander Vesel, 2013, drugi znanstveni članki Opis: The square ▫$G^2$▫ of a graph ▫$G$▫ is obtained from ▫$G$▫ by adding edges joining all pairs of nodes at distance 2 in ▫$G$▫. In this note we prove that ▫$chi((C_mBox C_n)^2) le 6$ for $m, n ge 40$▫. This confirms Conjecture 19 stated in [É. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327-2333].
Ključne besede: matematika, teorija grafov, kromatično število, kartezični produkt, označevanje grafov, kvadrat grafa, mathematics, graph theory, chromatic number, Cartesian product, graph labeling, square if a graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 1460; Prenosov: 83
 Povezava na celotno besedilo |
10. A note on the domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2011 Opis: Z uporabo algebraičnega pristopa implementiramo konstantni algoritem za računanje dominantnega števila kartezičnih produktov poti in ciklov. Podamo formule za dominantna števila ▫$gamma(P_n Box C_k)$▫ (za ▫$k leq 11$▫, ▫$n in {mathbb N}$)▫ in dominantna števila ▫$gamma(C_n Box P_k)$▫ in ▫$gamma(C_n Box C_k)$▫ (za ▫$k leq 6$▫, ▫$n in {mathbb N}$▫).
Ključne besede: teorija grafov, kartezični produkt, grid, torus, dominacija, algebra poti, konstantni algoritem, graph theory, Cartesian product, grid graph, torus, graph domination, path algebra, constant time algorithm
Objavljeno v DKUM: 10.07.2015; Ogledov: 1740; Prenosov: 40
Povezava na celotno besedilo |
