Results 11 to 20 of about 268 (119)
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
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
Semi-dynamic algorithms for strongly chordal graphs [PDF]
Discrete Mathematics, Algorithms and Applications, 2020 Within the broad ambit of algorithm design, the study of dynamic graph algorithms continues to be a thriving area of research. Commensurate with this interest is an extensive literature on the topic. Not surprisingly, dynamic algorithms for all varieties of shortest path problems, in view of their practical importance, occupy a preeminent position ...
Md. Zamilur Rahman, Asish Mukhopadhyay
openaire +2 more sources
On Minimum Maximal Distance-k Matchings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$
Yury Kartynnik, Andrew Ryzhikov
doaj +1 more source
Total Roman domination on the digraphs
Open Mathematics, 2023 Let D=(V,A)D=\left(V,A) be a simple digraph with vertex set VV, arc set AA, and no isolated vertex. A total Roman dominating function (TRDF) of DD is a function h:V→{0,1,2}h:V\to \left\{0,1,2\right\}, which satisfies that each vertex x∈Vx\in V with h(x ...
Zhang Xinhong, Song Xin, Li Ruijuan
doaj +1 more source
Complexity of Hamiltonian Cycle Reconfiguration
Algorithms, 2018 The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C 0 and C t of a graph G, whether there is a sequence of Hamiltonian cycles C 0 , C 1 , … , C t such that C i can be obtained ...
Asahi Takaoka
doaj +1 more source
Strongly chordal and chordal bipartite graphs are sandwich monotone
Journal of Combinatorial Optimization, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Pinar Heggernes +3 more
openaire +3 more sources
Discussiones Mathematicae Graph Theory, 2019 Several recent papers have investigated unichord-free graphs—the graphs in which no cycle has a unique chord. This paper proposes a concept of strongly unichord-free graph, defined by being unichord-free with no cycle of length 5 or more having exactly ...
McKee Terry A.
doaj +1 more source
Characterization of Super Strongly Perfect Graphs in Chordal and Strongly Chordal Graphs
Mapana - Journal of Sciences, 2012 A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. In this paper, we have investigated the characterization of Super Strongly Perfect graphs using odd cycles.
R Mary Jeya Jothi, A Amutha
openaire +2 more sources
Matching and multidimensional matching in chordal and strongly chordal graphs
Discrete Applied Mathematics, 1998 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Elias Dahlhaus, Marek Karpinski
openaire +2 more sources