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"”.

  1. 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 …

    byu Repository record for Minimum Rank Problems for Cographs (opens in a new tab) Download PDF for Minimum Rank Problems for Cographs (opens in a new tab)

  2. 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 …

    jhu Repository record for A Combinatorial Analysis of the Eigenvalues of the Laplacian Matrices of Cographs (opens in a new tab)

  3. 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 …

    lsu-thes Repository record for Characterizations of Certain Classes of Graphs and Matroids (opens in a new tab)

  4. 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 …

    waterloo Repository record for On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set (opens in a new tab)

  5. 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 …

    uvic Repository record for Graph partitions and the bichromatic number (opens in a new tab)

  6. 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 …

    calgary Repository record for Siblings of Binary Relations: The Case of Direct Sums of Chains, NE-Free Posets and Trees (opens in a new tab)

  7. 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 …

    ubc Repository record for A study on generalized solution concepts in constraint satisfaction and graph colouring (opens in a new tab) Download PDF for A study on generalized solution concepts in constraint satisfaction and graph colouring (opens in a new tab)

  8. 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 …

    ubc Repository record for Parallel techniques for construction of trees and related problems (opens in a new tab) Download PDF for Parallel techniques for construction of trees and related problems (opens in a new tab)

  9. 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.

    uvic Repository record for Mobile Guards’ Strategies for Graph Surveillance and Protection (opens in a new tab)

  10. 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 …

    qucosa-diss

  11. 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 …

    uvic Repository record for Complexity of frugal homomorphisms (opens in a new tab)

  12. 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 …

    greece Repository record for Algorithms and complexity of graph modification problems (opens in a new tab)

  13. 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 …

    greece Repository record for Algorithmic techniques for encoding permutations and permutation graphs for watermarking software, image, audio, and text (opens in a new tab)

  14. 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 …

    brazil-ufrgs Repository record for Número mínimo de autovalores distintos de um grafo (opens in a new tab)