The independence number alpha of a graph is the size of a maximum independent set of vertices. An independent set is a set of vertices where every pair of vertices in non-adjacent. This number is known to be hard to compute. The bound we worked with is defined as epsilon = max[e(v)-eh(v)] over all the vertices in the vertex set, V(G). e(v) is the number of vertices at even distance from v. eh(v) is the number of edges both of whose endpoints are at even distance from v. Epsilon can be calculated in polynomial time. Siemion Fajtlowicz proved that alpha is greater than or equal to epsilon for any graph. We worked to characterize graphs where alpha=epsilon.

The independence number of a graph is the maximum number of vertices from the vertex set of the graph such that no two vertices are adjacent. We systematically examine a collection of upper bounds for the independence number to determine graphs for which each upper bound is better than any other upper bound considered. A similar investigation follows for lower bounds. In several instances a graph cannot be found. We also include graphs for which no bound equals $\alpha$ and bounds which do not apply to general graphs.

In the 1970's computer scientists developed the theory of computational complexity. Some problems seemed hard-to-compute, while others were easy. It turned out that many of the hard problems were equally hard in a way that could be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was the first problem to be proved NP-complete in 1971. Since then numerous other hard-to-solve problems have been proved to be in NP-complete. In this paper we will examine the problem of how to find a maximum independent set of vertices for a graph. This problem is known as Maximum Independent Set (MIS) for a graph. The corresponding decision problem for MIS is the question, given an integer K, is there a independent set with at least K vertices? This decision problem is INDEPENDENT SET (IS). The intention of this paper is to show through polynomial transformation that IS is in the set of NP-complete Problems. We intend to show that 3SAT is NP-complete and then using this fact, that IS is NP-complete.

An independent set in a graph G is a set of pairwise nonadjacent vertices, and the maximum size, alpha(G), of an independent set in G is called the independence number. Given a graph G and weight matrix A of G with entries from some field F, the maximum dimension of an A-isotropic subspace, known as the Witt index of A, is an upper bound on alpha(G). Since any weight matrix can be used, it is natural to seek the minimum upper bound on the independence number of G that can be achieved by a weight matrix. This minimum, iota_F^*(G), is called the minimum Witt index of G over F, and the resulting bound, alpha(G)<= iota_F^*(G), is called the isotropic bound. When F is finite, the possible values of iota_F^*(G) are determined and the graphs that attain the isotropic bound are characterized. The characterization is given in terms of graph classes CC(n,t,c) and CK(n,t,k) constructed from certain spanning subgraphs called C(n,t,c)-graphs and K(n,t,k)-graphs. Here t is the term rank of the adjacency matrix of G. When F=R, the isotropic bound is known as the Cvetkovi\'c bound. It is shown that it is sufficient to consider a finite number of weight matrices A when determining iota_R^*(G) and that, in many cases, two weight values suffice. For example, if the vertex set of G can be covered by alpha(G) cliques, then G attains the Cvetkovi\'c bound with a weight matrix with two weight values. Inequalities on alpha and iota_F^* resulting from graph operations such as sums, products, vertex deletion, and vertex identification are examined and, in some cases, conditions that imply equality are proved. The equalities imply that the problem of determining whether or not alpha(G)=iota_F^*(G) can be reduced to that of determining iota_F^*(H) for certain crucial graphs H found from G. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2007-09-04 15:38:47.57

Let G = (V (G), E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆⊆ V (G) is called a global offensive k-alliance if ΙN(ν) ∩ SΙ ≥ ΙN(ν)-SΙ+k for every ν ε V (G)-S, where N(v) is the neighborhood of ν. The global offensive k-alliance number γko(G) is the minimum cardinality of a global o ensive k-alliance in G. We present di erent bounds on γko(G) in terms of order, maximum degree, independence number, chromatic number and minimum degree.

No description available.

Cette thèse étudie les aspects combinatoires, algorithmiques et la complexité de problèmes de théorie des graphes, et tout spécialement de problèmes liés aux notions de marches, de transitions et de distance dans les graphes. Nous nous intéressons d’abord au problème de traffic monitoring, qui consiste à placer aussi peu de capteurs que possible sur les arcs d’un graphe de façon à pouvoir reconstituer des marches d’objets. La caractérisation d’instances intéressantes dans la pratique nous amène à la notion de transitions interdites, qui renforce le modèle de graphe. Notre travail sur les graphes à transitions interdites comprend aussi l’étude de la notion d’ensemble de transitions connectant, que l’on peut voir comme l’analogue en terme de transitions de la notion d’arbre couvrant. Une partie importante de cette thèse porte sur les graphes géométriques, qui sont des graphes dont les sommets sont des points de l’espace réel et dont les arêtes sont déterminées par les distances géométriques entre les sommets. Ces graphes sont au coeur du célèbre problème de Hadwiger-Nelson et nous sont d’une grande aide dans notre étude de la densité des ensembles qui évitent la distance 1 dans plusieurs types d’espaces normés. Nous développons des outils pour étudier ces problèmes et les utilisons pour prouver la conjecture de Bachoc-Robins sur plusieurs paralléloèdres. Nous nous penchons aussi sur le cas du plan euclidien et améliorons les bornes sur la densité des ensembles évitant la distance 1 et sur son nombre chromatique fractionnaire. Enfin, nous étudions la complexité de problèmes d’homomorphismes de graphes et établissons des théorèmes de dichotomie sur la complexité des homomorphismes localement injectifs vers les tournois réflexifs. / This thesis studies combinatorial, algorithmic and complexity aspects of graph theory problems, and especially of problems related to the notions of walks, transitions and distances in graphs. We first study the problem of traffic monitoring, in which we have to place as few censors as possible on the arcs of a graph to be able to retrace walks of objects. The characterization of instances of practical interests brings us to the notion of forbidden transitions, which strengthens the model of graphs. Our work on forbidden-transition graphs also includes the study of connecting transition sets, which can be seen as a translation to forbidden-transition graphs of the notion of spanning trees. A large part of this thesis focuses on geometric graphs, which are graphs whose vertices are points of the real space and whose edges are determined by geometric distance between the vertices. This graphs are at the core of the famous Hadwiger- Nelson problem and are of great help in our study of the density of sets avoiding distance 1 in various normed spaces. We develop new tools to study these problems and use them to prove the Bachoc-Robins conjecture on several parallelohedra. We also investigate the case of the Euclidean plane and improve the bounds on the density of sets avoiding distance 1 and on its fractional chromatic number. Finally, we study the complexity of graph homomorphism problems and establish dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.