Results 61 to 70 of about 1,967 (126)
Exact and Heuristic Solution Approaches for the Cluster Deletion Problem on General Graphs
Networks, Volume 85, Issue 4, Page 351-367, June 2025.ABSTRACT A cluster graph is a disjoint union of cliques, obtained by clustering the nodes of a given network and then removing the edges between nodes assigned to different clusters. The Cluster Deletion problem asks for the smallest subset of edges to be removed from a network in order to produce a cluster graph, which is equivalent to determining the
Giuseppe Ambrosio +4 more
wiley +1 more source
On the Spectrum of Threshold Graphs
International Scholarly Research Notices, Volume 2011, Issue 1, 2011., 2011 The antiregular connected graph on r vertices is defined as the connected graph whose vertex degrees take the values of r − 1 distinct positive integers. We explore the spectrum of its adjacency matrix and show common properties with those of connected threshold graphs, having an equitable partition with a minimal number r of parts.
Irene Sciriha +6 more
wiley +1 more source
A survey on algorithmic aspects of modular decomposition
, 2009 The modular decomposition is a technique that applies but is not restricted to graphs. The notion of module naturally appears in the proofs of many graph theoretical theorems. Computing the modular decomposition tree is an important preprocessing step to
Habib, Michel, Paul, Christophe
core +3 more sources
Siblings of countable cographs
, 2020 We show that every countable cograph has either one or infinitely many siblings. This answers, very partially, a conjecture of Thomass . The main tools are the notion of well quasi ordering and the correspondence between cographs and some labelled ordered trees.
Gena, Hahn +2 more
openaire +3 more sources
Odd chromatic number of graph classes
Journal of Graph Theory, Volume 108, Issue 4, Page 722-744, April 2025.Abstract A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G $G$.
Rémy Belmonte +3 more
wiley +1 more source
On the Complexity of Role Colouring Planar Graphs, Trees and Cographs [PDF]
, 2014 We prove several results about the complexity of the role colouring problem. A role colouring of a graph $G$ is an assignment of colours to the vertices of $G$ such that two vertices of the same colour have identical sets of colours in their ...
Purcell, Christopher, Rombach, M. Puck
core
, 2006 "[M]athematicians care no more for logic than logicians for mathematics." Augustus de Morgan, 1868. Proofs are traditionally syntactic, inductively generated objects.
Hughes, Dominic
core +4 more sources
Eigenvalue location in cographs [PDF]
Discrete Applied Mathematics, 2018 We give an $O(n)$ time and space algorithm for constructing a diagonal matrix congruent to A+xI, where A is the adjacency matrix of a cograph and $x\in \mathbb{R}$. Applications include determining the number of eigenvalues of a cograph's adjacency matrix that lie in any interval, obtaining a formula for the inertia of a cograph, and exhibiting ...
David P. Jacobs +2 more
openaire +3 more sources
The complexity of the perfect matching‐cut problem
Journal of Graph Theory, Volume 108, Issue 3, Page 432-462, March 2025.Abstract PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four.
Valentin Bouquet, Christophe Picouleau
wiley +1 more source
On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions
, 2015 Symbolic ultrametrics define edge-colored complete graphs K_n and yield a simple tree representation of K_n. We discuss, under which conditions this idea can be generalized to find a symbolic ultrametric that, in addition, distinguishes between edges and
A Burstein +17 more
core +1 more source