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: 256
 Celotno besedilo (719,06 KB)
Gradivo ima več datotek! Več... |
2. Simplified computation of matchings in polygraphsAnte Graovac, Damir Vukičević, Damir Ježek, Janez Žerovnik, 2005, izvirni znanstveni članek Opis: Matching polynomial and perfect matchings for fasciagraphs, rotagraphs and twisted rotagraphs are treated in the paper. Classical transfer matrix approach makes it possible to get recursions for matching polynomial and perfect matchings, but the order of the matrix grows exponentially in the number of the linking edges between monographs. Novel transfer matrices are introduced whose order is much lower than that in classical transfer matrices. The virtue of the method introduced is especially pronounced when twoor more linking edges end in the same terminal vertex of a monograph. An example of a polyacene polygraph with extended pairings is given where a novel matrix has only 16 entries as compared to 65536 entries in the classical transfer matrix. However, all pairings are treated here on equal footing, but the method introduced can be applied to selected types of pairings of interest in chemistry.
Ključne besede: polygraphs, matching polynomial, matchings, perfect matchings, Kekulé structures, extended structures, recursive enumeration, transfer matrix method
Objavljeno v DKUM: 05.07.2017; Ogledov: 1583; Prenosov: 93
Celotno besedilo (102,97 KB)
Gradivo ima več datotek! Več... |
3. Computing the determinant and the algebraic structure count in polygraphsAnte Graovac, Martin Juvan, Bojan Mohar, Janez Žerovnik, 1999, izvirni znanstveni članek Opis: An algorithm for computing the algebraic structure count in polygraphs is presented. It expresses the related determinant of the adjacency matrix of a polygraph in terms of the determinants of monographs and bonding edges between the monographs. The algorithm is illustrated on a class of polygraphs with two bonding edges between monographs and computations for selected examples of polygraphs of this class are presented.
Ključne besede: mathematics, determinant, algebraic structure count, polygraphs, acenylenes, phenylenes
Objavljeno v DKUM: 05.07.2017; Ogledov: 1036; Prenosov: 129
Celotno besedilo (128,44 KB)
Gradivo ima več datotek! Več... |
4. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2011, izvirni znanstveni članek Opis: Rimska dominacija je zgodovinsko utemeljena različica običajne dominacije, pri kateri vozlišča grafa označimo z oznakami iz množice ▫${0,1,2}$▫ tako, da ima vsako vozlišče z oznako 0 soseda z oznako 2. Najmanjšo izmed vsot oznak grafa imenujemo rimsko dominantno število grafa. Z uporabo algebraičnega pristopa dobimo konstantni algoritem za računanje rimskega dominantnega števila posebne vrste poligrafov: rota- in fasciagrafov. V posebnih primerih izračunamo formule za rimsko dominanto število kartezičnega produkta poti in ciklov ▫$P_n Box P_k$▫, ▫$P_n Box C_k$▫ za ▫$k leq 8$▫ in ▫$n in {mathbb N}$▫ ter za ▫$C_n Box P_k$▫ in ▫$C_n Box C_k$▫ za ▫$k leq 5$▫, ▫$n in {mathbb N}$▫. Dodan je seznam rimskih grafov med kartezičnimi produkti zgoraj omenjenih poti in ciklov.
Ključne besede: teorija grafov, kartezični produkt, rimsko dominantno število, poligrafi, algebra poti, graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Objavljeno v DKUM: 10.07.2015; Ogledov: 1762; Prenosov: 75
 Povezava na celotno besedilo |
