Spelling suggestions: "subject:"redundance"" "subject:"irredundant""
1 |
Total Irredundance in GraphsFavaron, Odile, Haynes, Teresa W., Hedetniemi, Stephen T., Henning, Michael A., Knisley, Debra J. 28 September 2002 (has links)
No description available.
|
2 |
Broadcasts and multipackings in graphsTeshima, Laura Elizabeth 10 December 2012 (has links)
A broadcast is a function f that assigns an integer value to each vertex of a graph such that, for each v ∈ V , f (v) ≤ e (v), where e(v) is the eccentricity of v. The broadcast number of a graph is the minimum value of ∑ f(v) among all broadcasts f with the property that for each vertex u ∈ V, there exists some v ∈ V with f(v) > 0 such that d(υ,v) ≤ f(v). We present a new upper bound for the broadcast number of a graph in terms of its irredundance number and a new dual property of the broadcast number called the multipacking number of a graph. / Graduate
|
3 |
A Roman Domination ChainChellali, Mustapha, Haynes, Teresa W., Hedetniemi, Sandra M., Hedetniemi, Stephen T., McRae, Alice A. 01 January 2016 (has links)
For a graph (Formula presented.), a Roman dominating function (Formula presented.) has the property that every vertex (Formula presented.) with (Formula presented.) has a neighbor (Formula presented.) with (Formula presented.). The weight of a Roman dominating function (Formula presented.) is the sum (Formula presented.), and the minimum weight of a Roman dominating function on (Formula presented.) is the Roman domination number of (Formula presented.). In this paper, we define the Roman independence number, the upper Roman domination number and the upper and lower Roman irredundance numbers, and then develop a Roman domination chain parallel to the well-known domination chain. We also develop sharpness, strictness and bounds for the Roman domination chain inequalities.
|
4 |
The queen's domination problemBurger, Alewyn Petrus 11 1900 (has links)
The queens graph Qn has the squares of then x n chessboard as its vertices; two squares
are adjacent if they are in the same row, column or diagonal. A set D of squares of
Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a
square in D. If no two squares of a set I are adjacent then I is an independent set.
Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote
the minimum size of an independent dominating set of Qn. The main purpose of this
thesis is to determine new values for'!'( Qn). We begin by discussing the most important
known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known
values of 'J'(Qn) and explain how they were determined. We briefly explain how to
obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It
is often useful to study these small dominating sets to look for patterns and possible
generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 )
and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case
n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3,
thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper
bound')' (Qn) :s; 1
8
5n + 0 (1), which is better than known bounds in the literature and
in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8
we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6 / Mathematical Sciences / D.Phil. (Applied Mathematics)
|
5 |
Criticality of the lower domination parameters of graphsCoetzer, Audrey 03 1900 (has links)
Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2007. / In this thesis we focus on the lower domination parameters of a graph G, denoted ¼(G), for
¼ 2 {i, ir, °}. For each of these parameters, we are interested in characterizing the structure of
graphs that are critical when faced with small changes such as vertex-removal, edge-addition and
edge-removal. While criticality with respect to independence and domination have been well
documented in the literature, many open questions still remain with regards to irredundance.
In this thesis we answer some of these questions.
First we describe the relationship between transitivity and criticality. This knowledge we then
use to determine under which conditions certain classes of graphs are critical. Each of the
chosen classes of graphs will provide specific examples of different types of criticality. We also
formulate necessary conditions for graphs to be ir-critical and ir-edge-critical.
|
6 |
The queen's domination problemBurger, Alewyn Petrus 11 1900 (has links)
The queens graph Qn has the squares of then x n chessboard as its vertices; two squares
are adjacent if they are in the same row, column or diagonal. A set D of squares of
Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a
square in D. If no two squares of a set I are adjacent then I is an independent set.
Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote
the minimum size of an independent dominating set of Qn. The main purpose of this
thesis is to determine new values for'!'( Qn). We begin by discussing the most important
known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known
values of 'J'(Qn) and explain how they were determined. We briefly explain how to
obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It
is often useful to study these small dominating sets to look for patterns and possible
generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 )
and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case
n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3,
thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper
bound')' (Qn) :s; 1
8
5n + 0 (1), which is better than known bounds in the literature and
in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8
we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6 / Mathematical Sciences / D.Phil. (Applied Mathematics)
|
7 |
Critical concepts in domination, independence and irredundance of graphsGrobler, Petrus Jochemus Paulus 11 1900 (has links)
The lower and upper independent, domination and irredundant numbers of the graph
G = (V, E) are denoted by i ( G) , f3 ( G), 'Y ( G), r ( G), ir ( G) and IR ( G) respectively.
These six numbers are called the domination parameters. For each of these parameters
n:, we define six types of criticality. The graph G is n:-critical (n:+ -critical) if the
removal of any vertex of G causes n: (G) to decrease (increase), G is n:-edge-critical
(n:+-edge-critical) if the addition of any missing edge causes n: (G) to decrease (increase),
and G is Ir-ER-critical (n:- -ER-critical) if the removal of any edge causes
n: (G) to increase (decrease). For all the above-mentioned parameters n: there exist
graphs which are n:-critical, n:-edge-critical and n:-ER-critical. However, there do not
exist any n:+-critical graphs for n: E {ir,"f,i,/3,IR}, no n:+-edge-critical graphs for
n: E {ir,"f,i,/3} and non:--ER-critical graphs for: E {'Y,/3,r,IR}. Graphs which
are "I-critical, i-critical, "I-edge-critical and i-edge-critical are well studied in the literature.
In this thesis we explore the remaining types of criticality.
We commence with the determination of the domination parameters of some wellknown
classes of graphs. Each class of graphs we consider will turn out to contain a
subclass consisting of graphs that are critical according to one or more of the definitions
above. We present characterisations of "I-critical, i-critical, "I-edge-critical and
i-edge-critical graphs, as well as ofn:-ER-critical graphs for n: E {/3,r,IR}. These
characterisations are useful in deciding which graphs in a specific class are critical.
Our main results concern n:-critical and n:-edge-critical graphs for n: E {/3, r, IR}. We show that the only /3-critical graphs are the edgeless graphs and that a graph is IRcritical
if and only if it is r-critical, and proceed to investigate the r-critical graphs
which are not /3-critical. We characterise /3-edge-critical and r-edge-critical graphs
and show that the classes of IR-edge-critical and r-edge-critical graphs coincide. We also exhibit classes of r+ -critical, r+ -edge-critical and i- -ER-critical graphs. / Mathematical Sciences / D. Phil. (Mathematics)
|
8 |
Critical concepts in domination, independence and irredundance of graphsGrobler, Petrus Jochemus Paulus 11 1900 (has links)
The lower and upper independent, domination and irredundant numbers of the graph
G = (V, E) are denoted by i ( G) , f3 ( G), 'Y ( G), r ( G), ir ( G) and IR ( G) respectively.
These six numbers are called the domination parameters. For each of these parameters
n:, we define six types of criticality. The graph G is n:-critical (n:+ -critical) if the
removal of any vertex of G causes n: (G) to decrease (increase), G is n:-edge-critical
(n:+-edge-critical) if the addition of any missing edge causes n: (G) to decrease (increase),
and G is Ir-ER-critical (n:- -ER-critical) if the removal of any edge causes
n: (G) to increase (decrease). For all the above-mentioned parameters n: there exist
graphs which are n:-critical, n:-edge-critical and n:-ER-critical. However, there do not
exist any n:+-critical graphs for n: E {ir,"f,i,/3,IR}, no n:+-edge-critical graphs for
n: E {ir,"f,i,/3} and non:--ER-critical graphs for: E {'Y,/3,r,IR}. Graphs which
are "I-critical, i-critical, "I-edge-critical and i-edge-critical are well studied in the literature.
In this thesis we explore the remaining types of criticality.
We commence with the determination of the domination parameters of some wellknown
classes of graphs. Each class of graphs we consider will turn out to contain a
subclass consisting of graphs that are critical according to one or more of the definitions
above. We present characterisations of "I-critical, i-critical, "I-edge-critical and
i-edge-critical graphs, as well as ofn:-ER-critical graphs for n: E {/3,r,IR}. These
characterisations are useful in deciding which graphs in a specific class are critical.
Our main results concern n:-critical and n:-edge-critical graphs for n: E {/3, r, IR}. We show that the only /3-critical graphs are the edgeless graphs and that a graph is IRcritical
if and only if it is r-critical, and proceed to investigate the r-critical graphs
which are not /3-critical. We characterise /3-edge-critical and r-edge-critical graphs
and show that the classes of IR-edge-critical and r-edge-critical graphs coincide. We also exhibit classes of r+ -critical, r+ -edge-critical and i- -ER-critical graphs. / Mathematical Sciences / D. Phil. (Mathematics)
|
9 |
Vertex Sequences in GraphsHaynes, Teresa W., Hedetniemi, Stephen T. 01 January 2021 (has links)
We consider a variety of types of vertex sequences, which are defined in terms of a requirement that the next vertex in the sequence must meet. For example, let S = (v1, v2, …, vk ) be a sequence of distinct vertices in a graph G such that every vertex vi in S dominates at least one vertex in V that is not dominated by any of the vertices preceding it in the sequence S. Such a sequence of maximal length is called a dominating sequence since the set {v1, v2, …, vk } must be a dominating set of G. In this paper we survey the literature on dominating and other related sequences, and propose for future study several new types of vertex sequences, which suggest the beginning of a theory of vertex sequences in graphs.
|
10 |
Etude, représentation et applications des traverses minimales d'un hypergraphe / Representation and applications of hypergraph minimal transversalsJelassi, Mohamed Nidhal 08 December 2014 (has links)
Cette thèse s'inscrit dans le domaine de la théorie des hypergraphes et s'intéresse aux traverses minimales des hypergraphes. L'intérêt pour l'extraction des traverses minimales est en nette croissance, depuis plusieurs années, et ceci est principalement dû aux solutions qu'offrent les traverses minimales dans divers domaines d'application comme les bases de données, l'intelligence artificielle, l'e-commerce, le web sémantique, etc. Compte tenu donc du large éventail des domaines d'application des traverses minimales et de l'intérêt qu'elles suscitent, l'objectif de cette thèse est donc d'explorer de nouvelles pistes d'application des traverses minimales tout en proposant des méthodes pour optimiser leur extraction. Ceci a donné lieu à trois contributions proposées dans cette thèse. La première approche tend à tirer profit de l'émergence du Web 2.0 et, par conséquent, des réseaux sociaux en utilisant les traverses minimales pour la détection des acteurs importants au sein de ces réseaux. La deuxième partie de recherche au cours de cette thèse s'est intéressé à la réduction du nombre de traverses minimales d'un hypergraphe. Ce nombre étant très élevé, une représentation concise et exacte des traverses minimales a été proposée et est basée sur la construction d'un hypergraphe irrédondant, d'où sont calculées les traverses minimales irrédondantes de l'hypergraphe initial. Une application de cette représentation au problème de l'inférence des dépendances fonctionnelles a été présentée pour illustrer l’intérêt de cette approche. La dernière approche s'est intéressée à la décomposition des hypergraphes en des hypergraphes partiels. Les traverses minimales de ces derniers sont calculées et leur produit cartésien permet de générer l'ensemble des traverses de l'hypergraphe. Les différentes études expérimentales menées ont montré l’intérêt de ces approches proposées / This work is part of the field of the hypergraph theory and focuses on hypergraph minimal transversal. The problem of extracting the minimal transversals from a hypergraph received the interest of many researchers as shown the number of algorithms proposed in the literature, and this is mainly due to the solutions offered by the minimal transversal in various application areas such as databases, artificial intelligence, e-commerce, semantic web, etc. In view of the wide range of fields of minimal transversal application and the interest they generate, the objective of this thesis is to explore new application paths of minimal transversal by proposing methods to optimize the extraction. This has led to three proposed contributions in this thesis. The first approach takes advantage of the emergence of Web 2.0 and, therefore, social networks using minimal transversal for the detection of important actors within these networks. The second part of research in this thesis has focused on reducing the number of hypergraph minimal transversal. A concise and accurate representation of minimal transversal was proposed and is based on the construction of an irredundant hypergraph, hence are calculated the irredundant minimal transversal of the initial hypergraph. An application of this representation to the dependency inference problem is presented to illustrate the usefulness of this approach. The last approach includes the hypergraph decomposition into partial hypergraph the “local” minimal transversal are calculated and their Cartesian product can generate all the hypergraph transversal sets. Different experimental studies have shown the value of these proposed approaches
|
Page generated in 0.0595 seconds