Algebra poti in dominantni problemi na grafovskih produktih

Pavlič, Polona

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Algebra poti in dominantni problemi na grafovskih produktih
Authors:	ID Pavlič, Polona (Author) ID Žerovnik, Janez (Mentor) More about this mentor...
Files:	DR_Pavlic_Polona_2013.pdf (1,51 MB) MD5: 3A85A43525F5A485C3548E8B91E76E68 PID: 20.500.12556/dkum/1ee39f50-628d-493f-8777-d17b6ec3cb9e
Language:	Slovenian
Work type:	Dissertation
Typology:	2.08 - Doctoral Dissertation
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	Različni problemi grafovskih invariant predstavljajo velik del študij na področju teorije grafov. Ker so ti problemi v veliki meri NP-polni, je smiselno iskati rešitve na določenih zanimivih družinah grafov. V tem delu se omejimo na probleme dominacije na družini poligrafov. To so grafi, ki izhajajo iz kemijske teorije grafov in so matematični model kemijske strukture polimera. V kemiji je polimer makromolekula, ki ima posebno ponavljajočo se strukturo molekul, povezanih s kovalentnimi vezmi. Mi se posebej omejimo na primere, ko so te ponavljajoče enote enake, oziroma v jeziku teorije grafov, ko so monografi izomorfni, ter so povezave med njimi enake. Taki grafi se imenujejo rotagrafi, če pa med prvim in zadnjim monografom ni povezav, imenujemo tak poligraf fasciagraf. S pomočjo algebre poti pokažemo, da se različni problemi dominacije na razredu poligrafov za fiksno velikost monografa lahko rešijo v konstantnem času. Ker so posebni primeri poligrafov tudi grafovski produkti poti in ciklov, za kartezični in direktni produkt implementiramo algoritem in dobimo formule za dominantna, neodvisna dominantna ter rimska dominantna števila teh grafov, kjer je eden od faktorjev fiksen. Nadalje pokažemo, da se preučevane grafovske invariante na fasciagrafih in rotagrafih, pri katerih je monograf enak, lahko razlikujejo le za konstantno vrednost, natančneje, za končno število (različnih) konstant. Nazadnje še rešimo problem rimskega dominantnega števila na leksikografskem produktu grafov. Z vpeljavo koncepta tako imenovanih dominatnih parov za poljubna grafa podamo formulo, ki določi rimsko dominantno število njunega leksikografskega produkta. Podamo tudi nove neskončne družine rimskih grafov.
Keywords:	grafovski produkt, dominacija, algebra poti, konstantni algoritem, mreža, torus
Place of publishing:	[Maribor
Publisher:	P. Pavlič]
Year of publishing:	2013
PID:	20.500.12556/DKUM-40005
UDC:	519.17(043.3)
COBISS.SI-ID:	19789064
NUK URN:	URN:SI:UM:DK:G9UIGGV9
Publication date in DKUM:	04.04.2013
Views:	2952
Downloads:	248
Metadata:
Categories:	FNM
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:	English
Title:	Path algebra and domination problems on graph products
Abstract:	The problem of determining various graph invariants on graphs is one of the major research topics in graph theory. As most of these problems are NP-complete, it is interesting to look for algorithms on different graph classes. In this thesis we will restrict our attention to domination problems on the class of polygraphs. Polygraphs represent a mathematical model for a chemical structure called polymer, that is a molecule, whose structure is composed of multiple repeated units linked by covalent chemical bonds. We will focus on cases where these repeated units are the same, i.e. in graph theoretic terminology, where monographs are isomorphic and edges joining them are the same. Such graphs are known as rotagraphs. If there are no edges between the first and the last copy of the monograph, we refer to such polygraph with the name fasciagraf. Using an algebraic approach we show that many domination problems on the class of polygraphs, where the size of the monograph is fixed, can be solved in constant time. As polygraphs include products of paths and cycles, we implement the algorithm to get closed expressions for the domination, the independent domination and the Roman domination number of the Cartesian and the direct product of paths and cycles, where the size of one factor is fixed. Additionally we show that the values of the investigated graph invariants on the fasciagraphs and the rotagraphs with the same monograph can only differ for a constant value. Using a new concept of the so-called dominating couple we establish the Roman domination number of the lexicographic product of graphs. We also give new infinite classes of Roman graphs among investigated graphs.
Keywords:	graph product, domination, path algebra, a constant time algorithm, grids, tori

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back