Results 51 to 60 of about 1,423 (126)
The complexity of dominating set reconfiguration
, 2015 Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$ whose cardinalities are at most a given threshold $k$. Then, we are asked whether there exists a sequence of dominating sets of $G$ between $D_s$ and $D_t$ such that each ...
A Suzuki +11 more
core +1 more source
A linear algorithm for obtaining the Laplacian eigenvalues of a cograph [PDF]
, 2023 Chen, Guantao, Tura, Fernando C.
openalex +1 more source
Limits of Structures and the Example of Tree-Semilattices [PDF]
, 2015 The notion of left convergent sequences of graphs introduced by Lov\' asz et al. (in relation with homomorphism densities for fixed patterns and Szemer\'edi's regularity lemma) got increasingly studied over the past $10$ years.
Charbit, Pierre +2 more
core +4 more sources
An FPT Algorithm for Directed Co-Graph Edge Deletion
AlgorithmsIn the directed co-graph edge-deletion problem, we are given a directed graph and an integer k, and the question is whether we can delete, at most, k edges so that the resulting graph is a directed co-graph. In this paper, we make two minor contributions.
Wenjun Li +3 more
doaj +1 more source
On some Graphs with a Unique Perfect Matching
, 2017 We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O(m)$ if $G$ is either a cograph, or a split graph, or an interval graph, or claw-free ...
Chaplick, S. +3 more
core +1 more source
On the (non-)existence of polynomial kernels for Pl-free edge modification problems
, 2010 Given a graph G = (V,E) and an integer k, an edge modification problem for a graph property P consists in deciding whether there exists a set of edges F of size at most k such that the graph H = (V,E \vartriangle F) satisfies the property P.
A. Natanzon +16 more
core +2 more sources
Forbidden subgraphs of TI-power graphs of finite groups
Open MathematicsGiven a finite group GG with identity ee, the TI-power graph (trivial intersection power graph) defined on GG, denoted by Γ(G)\Gamma \left(G), is an undirected graph with vertex set GG where distinct vertices aa and bb are adjacent if ⟨a⟩∩⟨b⟩={e}\langle ...
Li Huani, Chen Jin, Lin Shixun
doaj +1 more source
Graph-Based Feature Crossing to Enhance Recommender Systems
MathematicsIn recommendation tasks, most existing models that learn users’ preferences from user–item interactions ignore the relationships between items. Additionally, ensuring that the crossed features capture both global graph structures and local context is non-
Congyu Cai +5 more
doaj +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