Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 14 of 14 for “"Cographs"”.
-
Minimum Rank Problems for Cographs
… nil vertices in general and nil vertices in cographs and prove that cographs with a nil vertex of a particular form contain two other nil vertices symmetric to the first. I discuss several open questions relating to these results and a counterexample. I prove that for all cographs G without …
-
A Combinatorial Analysis of the Eigenvalues of the Laplacian Matrices of Cographs
Cographs, also known as complement reducible graphs or decomposable graphs, are a recursively defined class of graphs built from a single vertex by the operations of disjoint union and join. The eigenvalues of a cograph's Laplacian matrix are nonnegative integers. In this thesis, we explore the …
-
Characterizations of Certain Classes of Graphs and Matroids
… subgraph is not 2-connected. The class of 2-cographs is closed under induced minors. We characterize the class of non-2-cographs for which every proper induced minor is a 2-cograph. We further find the finitely many members of this class whose complements are also induced-minor-minimal …
-
On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set
… trees, bipartite graphs, chordal graphs, and cographs. Then, we prove that the Cluster Vertex Deletion Reconfiguration problem is linear-time solvable for paths and trees, and that it is NP-hard on bipartite graphs, and PSPACE-complete in general. Finally, we determine that the Dominating Set …
-
Graph partitions and the bichromatic number
… for calculating the $(k,l)$-colourability of cographs and show that cographs have a particularly nice representation with regard to $(k,l)$-colourings. For proper circular arc graphs, we provide a method for $(k,l)$-colouring if $l \geq 1$, and establish an algebraic characterization for all …
-
Siblings of Binary Relations: The Case of Direct Sums of Chains, NE-Free Posets and Trees
… Thomasse conjecture was proved for countable cographs by Hahn, Pouzet and Woodrow. In order to tackle the conjectures towards posets, we verify both Thomasse's conjecture and its alternate version for direct sums of chains. We also show that the alternate Thomasse conjecture is true for …
-
A study on generalized solution concepts in constraint satisfaction and graph colouring
… colouring, where each colour class is a cograph. Cographs are the minimum family of graphs containing a single vertex and are closed under complementation and disjoint union. We define the cogchromatic number of a graph G as the minimum number of colours needed by a cograph colouring of G. Several …
-
Parallel techniques for construction of trees and related problems
… for graphs in the family of graphs known as cographs. In the tree synthesis method, we start with a forest of single node subtrees and construct a tree by adding edges or (for rooted trees) by creating parent nodes for some roots of the trees in the forest. We present a family of parallel and …
-
Mobile Guards’ Strategies for Graph Surveillance and Protection
… We further show that the eviction number of cographs can be computed in polynomial time. Finally, we study the length of both games when played on an n-vertex graph on which are located k guards; that is, the maximum number of turns required before a winner can be decided.
-
From Homologous Genes to Phylogenetic Species Trees
… tree representable sets of binary relations and cographs, symbolic ultrametrics, and so-called unp 2-structures is revealed. Based on the novel characterizations, polynomial-time recognition algorithms for tree representable sets of relations are presented. In the case, a set of relations is tree …
-
Complexity of frugal homomorphisms
… The improper closed 2-frugal chromatic number of cographs is determined, and a linear time algorithm for computing the improper closed 3-frugal chromatic number of a cograph is given. A linear time algorithm for computing the improper open 2-frugal chromatic number of a cograph is also given. Our …
-
Algorithms and complexity of graph modification problems
… classes of graphs: proper interval graphs, cographs, graphs with maximum degree 3, and graphs with bounded treewidth. To complement our result, we show that the problem remains NP-complete on the following graphs: split graphs, and consequently also on chordal graphs, graphs with maximum …
-
Algorithmic techniques for encoding permutations and permutation graphs for watermarking software, image, audio, and text
… and encodes the same permutation π* into several cographs C1[π*], C2[π*], …, Cn[π*]. Then, we present the algorithm Encode_Cograph.to.RPG, along with its corresponding decoding algorithm, which embeds a cograph into an RPG by exploiting the structure and some important algorithmic properties of …
-
Número mínimo de autovalores distintos de um grafo
Este trabalho explora o invariante espectral 𝑞(𝐺), ou seja, o número mínimo de autovalores distintos do grafo (𝐺), em grafos threshold, destacando a conexão entre a estrutura dos grafos e o espectro de matrizes simétricas associadas. Adotamos duas abordagens principais, primeiro estruturamos uma …