Results 31 to 40 of about 668 (63)
Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts.
Luerbio Faria +3 more
doaj +1 more source
An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs
Discussiones Mathematicae Graph Theory, 2019 Given a graph G = (V,E), the task in the vertex cover P3(V C P3) problem is to find a minimum subset of vertices F ⊆ V such that every path of order 3 in G contains at least one vertex from F.
Tu Jianhua, Shi Yongtang
doaj +1 more source
Irreversible 2-conversion set in graphs of bounded degree [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$
Jan Kynčl +2 more
doaj +1 more source
Corrigendum to "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3] [PDF]
Discrete Mathematics & Theoretical Computer ScienceIn this corrigendum, we give a counterexample to Theorem 5.2 in "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3]. We also present a polynomial-time algorithm for computing the monophonic rank of a starlike
Mitre C. Dourado +2 more
doaj +1 more source
Finite-dimensional Zinbiel algebras and combinatorial structures
Analele Stiintifice ale Universitatii Ovidius Constanta: Seria Matematica, 2022 In this paper, we study the link between finite-dimensional Zinbiel algebras and combinatorial structures or (pseudo)digraphs determining which configurations are associated with those algebras.
Ceballos Manuel +2 more
doaj +1 more source
The distribution of m-ary search trees generated by van der Corput sequences [PDF]
Discrete Mathematics & Theoretical Computer Science, 2004 We study the structure of $m$-ary search trees generated by the van der Corput sequences. The height of the tree is calculated and a generating function approach shows that the distribution of the depths of the nodes is asymptotically normal ...
Wolfgang Steiner
doaj +1 more source
On the smallest snarks with oddness 4 and connectivity 2 [PDF]
, 2018 A snark is a bridgeless cubic graph which is not 3-edge-colourable. The oddness of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph. Lukot'ka, M\'acajov\'a, Maz\'ak and \v{S}koviera showed in [Electron.
Goedgebeur, Jan
core +2 more sources
A Note on Graph Burning of Path Forests [PDF]
Discrete Mathematics & Theoretical Computer ScienceGraph burning is a natural discrete graph algorithm inspired by the spread of social contagion. Despite its simplicity, some open problems remain steadfastly unsolved, notably the burning number conjecture, which says that every connected graph of order $
Ta Sheng Tan, Wen Chean Teh
doaj +1 more source
Heuristic method to determine lucky k-polynomials for k-colorable graphs
Acta Universitatis Sapientiae: Informatica, 2019 The existence of edges is a huge challenge with regards to determining lucky k-polynomials of simple connected graphs in general. In this paper the lucky 3-polynomials of path and cycle graphs of order, 3 ≤ n ≤ 8 are presented as the basis for the ...
Kok Johan
doaj +1 more source
The Cartesian product of graphs with loops [PDF]
, 2014 We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi-Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one ...
Christiaan E. Van De Woestijne +7 more
core