Results 41 to 50 of about 10,951 (224)
On the multipacking number of grid graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 In 2001, Erwin introduced broadcast domination in graphs. It is a variant of classical domination where selected vertices may have different domination powers. The minimum cost of a dominating broadcast in a graph $G$ is denoted $\gamma_b(G)$.
Laurent Beaudou, Richard C. Brewster
doaj +1 more source
On chordal graph and line graph squares [PDF]
Discrete Applied Mathematics, 2018 In this work we investigate the chordality of squares and line graph squares of graphs. We prove a sufficient condition for the chordality of squares of graphs not containing induced cycles of length at least five. Moreover, we characterize the chordality of graph squares by forbidden subgraphs.
Robert Scheidweiler +1 more
openaire +2 more sources
Graph Decompositions and Factorizing Permutations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2002 A factorizing permutation of a given graph is simply a permutation of the vertices in which all decomposition sets appear to be factors. Such a concept seems to play a central role in recent papers dealing with graph decomposition. It is applied here for
Christian Capelle +2 more
doaj +3 more sources
A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs [PDF]
, 2019 A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected sub- graph in G.
CALAMONERI, Tiziana +2 more
core +1 more source
Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A graph $G$ is {\em matching-decyclable} if it has a matching $M$ such that $G-M$ is acyclic. Deciding whether $G$ is matching-decyclable is an NP-complete problem even if $G$ is 2-connected, planar, and subcubic.
Fábio Protti, Uéverton S. Souza
doaj +1 more source
Chordal Editing is Fixed-Parameter Tractable [PDF]
, 2014 Graph modification problems typically ask for a small set of operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property ...
A Hajnal +19 more
core +2 more sources
, 2013 It is shown that if the binomial edge ideal of a graph $G$ defines a Koszul algebra, then $G$ must be chordal and claw free.
A. Conca +16 more
core +1 more source
The Electronic Journal of CombinatoricsA hole in a graph is an induced subgraph which is a cycle of length at least four. A graph is chordal if it contains no holes. Following McKee and Scheinerman (1993), we define the chordality of a graph $G$ to be the minimum number of chordal graphs on $V(G)$ such that the intersection of their edge sets is equal to $E(G)$.
Chaniotis, Aristotelis +2 more
openaire +2 more sources
Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A path in an edge-colored graph $G$ is rainbow if no two edges of it are colored the same. The graph $G$ is rainbow-connected if there is a rainbow path between every pair of vertices.
Melissa Keranen, Juho Lauri
doaj +1 more source
Clique cutsets beyond chordal graphs [PDF]
Electronic Notes in Discrete Mathematics, 2017 Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed.
Boncompagni, V, Penev, I, Vušković, K
openaire +5 more sources