Results 1 to 10 of about 668 (63)
On the monophonic rank of a graph [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 A set of vertices $S$ of a graph $G$ is {\em monophonically convex} if every induced path joining two vertices of $S$ is contained in $S$. The {\em monophonic convex hull of $S$}, $\langle S \rangle$, is the smallest monophonically convex set containing $
Mitre C. Dourado +2 more
doaj +1 more source
Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets
Discussiones Mathematicae Graph Theory, 2021 A subset D ⊆ VG is a dominating set of G if every vertex in VG – D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching.
Henning Michael A., Topp Jerzy
doaj +1 more source
Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 In this paper, we study a variant of graph domination known as $(t, r)$ broadcast domination, first defined in Blessing, Insko, Johnson, and Mauretour in 2015.
Tom Shlomi
doaj +1 more source
The Neighborhood Polynomial of Chordal Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 We study the neighborhood polynomial and the complexity of its computation for chordal graphs. The neighborhood polynomial of a graph is the generating function of subsets of its vertices that have a common neighbor.
Helena Bergold +2 more
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2022 A 2-rainbow dominating function (2RDF) of a graph G is a function g from the vertex set V (G) to the family of all subsets of {1, 2} such that for each vertex v with g(v) =∅ we have ∪u∈N(v) g(u) = {1, 2}.
Poureidi Abolfazl, Rad Nader Jafari
doaj +1 more source
Compression with wildcards: All exact or all minimal hitting sets
Open Mathematics, 2023 Our objective is the compressed enumeration (based on wildcards) of all minimal hitting sets of general hypergraphs. To the author’s best knowledge, the only previous attempt towards compression, due to Toda, is based on binary decision diagrams and much
Wild Marcel
doaj +1 more source
Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 An equitable coloring of a graph $G=(V,E)$ is a (proper) vertex-coloring of $G$, such that the sizes of any two color classes differ by at most one. In this paper, we consider the equitable coloring problem in block graphs.
Hanna Furmańczyk, Vahan Mkrtchyan
doaj +1 more source
Determining the Hausdorff Distance Between Trees in Polynomial Time [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 The Hausdorff distance is a relatively new measure of similarity of graphs. The notion of the Hausdorff distance considers a special kind of a common subgraph of the compared graphs and depends on the structural properties outside of the common subgraph.
Aleksander Kelenc
doaj +1 more source
Cyclic Partitions of Complete and Almost Complete Uniform Hypergraphs
Discussiones Mathematicae Graph Theory, 2022 We consider cyclic partitions of the complete k-uniform hypergraph on a finite set V, minus a set of s edges, s ≥ 0. An s-almost t-complementary k-hypergraph is a k-uniform hypergraph with vertex set V and edge set E for which there exists a permutation ...
Dilbarjot, Gosselin Shonda Dueck
doaj +1 more source
Trees Whose Even-Degree Vertices Induce a Path are Antimagic
Discussiones Mathematicae Graph Theory, 2022 An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . ., |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v.
Lozano Antoni +3 more
doaj +1 more source