Results 31 to 40 of about 438 (125)
A Linear Recognition Algorithm for Cographs
SIAM Journal on Computing, 1985 Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination scheduling and automatic clustering of index terms ...
Corneil, D. G., Perl, Y., Stewart, L. K.
openaire +2 more sources
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
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
An efficient g‐centroid location algorithm for cographs
International Journal of Mathematics and Mathematical Sciences, Volume 2005, Issue 9, Page 1405-1413, 2005., 2005 In 1998, Pandu Rangan et al. Proved that locating the g‐centroid for an arbitrary graph is 𝒩𝒫‐hard by reducing the problem of finding the maximum clique size of a graph to the g‐centroid location problem. They have also given an efficient polynomial time algorithm for locating the g‐centroid for maximal outerplanar graphs, Ptolemaic graphs, and split ...
V. Prakash
wiley +1 more source
The Electronic Journal of Combinatorics, 2003 The rank of the adjacency matrix of a graph is bounded above by the number of distinct non-zero rows of that matrix. In general, the rank is lower than this number because there may be some non-trivial linear combination of the rows equal to zero. We show the somewhat surprising result that this never occurs for the class of cographs.
openaire +2 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
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
On the Edge‐Density of the Brownian Co‐Graphon and Common Ancestors of Pairs in the CRT
Random Structures &Algorithms, Volume 66, Issue 1, January 2025.ABSTRACT Bassino et al. have shown that uniform random co‐graphs (graphs without induced P4$$ {P}_4 $$) of size n$$ n $$ converge to a certain non‐deterministic graphon. The edge density of this graphon is a random variable Λ∈[0,1]$$ \boldsymbol{\Lambda} \in \left[0,1\right] $$ whose first moments have been computed by these authors.
Guillaume Chapuy
wiley +1 more source
Scheduling on uniform machines with a conflict graph: complexity and resolution
International Transactions in Operational Research, Volume 31, Issue 2, Page 863-888, March 2024.Abstract This paper deals with the problem of scheduling a set of unit‐time jobs on a set of uniform machines. The jobs are subject to conflict constraints modeled by a graph G called the conflict graph, in which adjacent jobs cannot be processed on a same machine.
Amin Mallek, Mourad Boudhar
wiley +1 more source