Iskanje po katalogu digitalne knjižnice

Opis: A function f that assigns values from the set to each vertex of a graph G is called a 2-rainbow independent dominating function, if the vertices assigned the value 1 form an independent set, the vertices assigned the value 2 form another independent set, and every vertex to which 0 is assigned has at least one neighbor in each of the mentioned independent sets. The weight of this function is the total number of vertices assigned nonzero values. The 2-rainbow independent domination number of G, , is the minimum weight of such a function. Motivated by a real-life application, we study the 2-rainbow independent domination number of the complementary prism of a graph G, which is constructed by taking G and its complement , and then adding edges between corresponding vertices. We provide tight bounds for , and characterize graphs for which the lower bound, i.e. , is attained. The obtained results can, in practice, enable the prediction of the cost estimate for a given communication or surveillance network.
Ključne besede: graph theory, domination, 2-rainbow independent domination, complementary prism
Objavljeno v DKUM: 23.04.2025; Ogledov: 0; Prenosov: 3
Celotno besedilo (366,59 KB)

Opis: Let ▫$G=(V,E)$▫ be a graph. A set of vertices ▫$A$▫ is an incidence generator for ▫$G$▫ if for any two distinct edges ▫$e,f \in E(G)$▫ there exists a vertex from ▫$A$▫ which is an endpoint of either ▫$e$▫ or ▫$f$▫. The smallest cardinality of an incidence generator for ▫$G$▫ is called the incidence dimension and is denoted by ▫$\dim_I(G)$▫. A set of vertices ▫$P \subseteq V(G)$▫ is a 2-packing of ▫$G$▫ if the distance in ▫$G$▫ between any pair of distinct vertices from ▫$P$▫ is larger than two. The largest cardinality of a 2-packing of ▫$G$▫ is the packing number of ▫$G$▫ and is denoted by ▫$\rho(G)$▫. In this article, the incidence dimension is introduced and studied. The given results show a close relationship between ▫$\dim_I(G)$▫ and ▫$\rho(G)$▫. We first note that the complement of any 2-packing in graph ▫$G$▫ is an incidence generator for ▫$G$▫, and further show that either ▫$\dim_I(G)=|V(G)|-\rho(G)$▫ or ▫$\dim_I(G)=|V(G)-|\rho(G)-1$▫ for any graph ▫$G$▫. In addition, we present some bounds for ▫$\dim_I(G)$▫ and prove that the problem of determining the incidence dimension of a graph is NP-hard.
Ključne besede: incidence dimension, incidence generator, 2-packing
Objavljeno v DKUM: 18.08.2023; Ogledov: 317; Prenosov: 43
Celotno besedilo (434,03 KB)
Gradivo ima več datotek! Več...

Opis: The booklet contains the abstracts of the talks given at the 22th Hereditarnia Workshop on Graph Properties that was held at the Faculty of Electrical Engineering and Computer Science in Maribor on 21st and 22nd of June, 2019. The workshop attracted 22 participants from 8 countries. All of the participants are researchers in di˙erent areas of graph theory, but at this event they all presented topics connected with (hereditary) graph properties. Themes of the talks encompass a wide range of contemporary graph theory research, notably, various types of graph colorings, graph domination, some graph dimensions matchings and graph products. Beside the abstracts of the plenary speaker (Roman Sotak) and three invited speakers (Tanja Gologranc, Michael A. Henning and Ismael G. Yero), the booklet also contains the abstracts of 7 contributed talks given at the event.
Ključne besede: mathematics, graph theory, Hereditarnia, Maribor, Slovenia
Objavljeno v DKUM: 13.12.2019; Ogledov: 1350; Prenosov: 359
Celotno besedilo (1,08 MB)
Gradivo ima več datotek! Več...

Opis: Tema magistrskega dela je risanje grafov z algoritmi na osnovi sil. V delu predstavimo različne algoritme za risanje grafov na osnovi sil: Tuttovo baricentrično metodo, algoritem Kamada-Kawai, algoritem Fruchtermana in Reingolda, Eadesov algoritem in algoritme za velike grafe. Magistrsko delo je razdeljeno v tri dele. V prvem delu so navedeni osnovni pojmi in definicije. Drugi del se začne s kratkim zgodovinskim pregledom algoritmov za risanje grafov na osnovi sil. Nato so opisani glavni algoritmi in zapisane tudi njihove psevdokode. Zaključimo s kratkim opisom implementacije Tuttove baricentrične metode in algoritma Fruchtermana in Reingolda ter prikažemo rezultate oz. več primerov izrisa grafov s pomočjo teh dveh programov.
Ključne besede: algoritmi, algoritmi na osnovi sil, grafi, risanje grafov
Objavljeno v DKUM: 13.10.2015; Ogledov: 5340; Prenosov: 350
Celotno besedilo (879,65 KB)