Results 31 to 40 of about 703 (75)
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
Discussiones Mathematicae Graph Theory, 2017 We characterize the class L32$L_3^2 $ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs.
Metelsky Yury +2 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
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
$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses [PDF]
Discrete Mathematics & Theoretical Computer ScienceA graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs.
Fernando Esteban Contreras-Mendoza +1 more
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
Recognition of chordal graphs and cographs which are Cover-Incomparability graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceCover-Incomparability graphs (C-I graphs) are an interesting class of graphs from posets. A C-I graph is a graph from a poset $P=(V,\le)$ with vertex set $V$, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of ...
Arun Anil, Manoj Changat
doaj +1 more source
Evasive Properties of Sparse Graphs and Some Linear Equations in Primes
, 2013 We give an unconditional version of a conditional, on the Extended Riemann Hypothesis, result of L. Babai, A. Banerjee, R. Kulkarni and V. Naik (2010) on the evasiveness of sparse graphs.Comment: This version corrects a mistake made in the previous ...
Shparlinski, Igor
core +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
A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
Special MatricesIn this article, we give an O(n)O\left(n) time and space algorithm for obtaining the Laplacian eigenvalues of a cograph. This approach is more efficient as there is no need to directly compute the eigenvalues of Laplacian matrix related to this class of ...
Chen Guantao, Tura Fernando C.
doaj +1 more source