Results 41 to 50 of about 855 (105)
Low-Degree Spanning Trees of Small Weight [PDF]
, 1996 The degree-d spanning tree problem asks for a minimum-weight spanning tree in which the degree of each vertex is at most d. When d=2 the problem is TSP, and in this case, the well-known Christofides algorithm provides a 1.5-approximation algorithm ...
Balaji Raghavachari +3 more
core +6 more sources
On q-Power Cycles in Cubic Graphs
Discussiones Mathematicae Graph Theory, 2017 In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic
Bensmail Julien
doaj +1 more source
Annular and pants thrackles [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A thrackle is a drawing of a graph in which each pair of edges meets precisely once. Conway's Thrackle Conjecture asserts that a thrackle drawing of a graph on the plane cannot have more edges than vertices.
Grace Misereh, Yuri Nikolayevsky
doaj +1 more source
Structural Properties of Recursively Partitionable Graphs with Connectivity 2
Discussiones Mathematicae Graph Theory, 2017 A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices.
Baudon Olivier +3 more
doaj +1 more source
Super edge-connectivity and matching preclusion of data center networks [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Edge-connectivity is a classic measure for reliability of a network in the presence of edge failures. $k$-restricted edge-connectivity is one of the refined indicators for fault tolerance of large networks.
Huazhong Lü, Tingzeng Wu
doaj +1 more source
Unique perfect matchings, forbidden transitions and proof nets for linear logic with Mix [PDF]
Logical Methods in Computer Science, 2020 This paper establishes a bridge between linear logic and mainstream graph theory, building on previous work by Retor\'e (2003). We show that the problem of correctness for MLL+Mix proof nets is equivalent to the problem of uniqueness of a perfect ...
Lê Thành Dũng Nguyên
doaj +1 more source
Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 We study Markov chains for $\alpha$-orientations of plane graphs, these are orientations where the outdegree of each vertex is prescribed by the value of a given function $\alpha$.
Stefan Felsner, Daniel Heldt
doaj +1 more source
On characteristic and permanent polynomials of a matrix
Special Matrices, 2017 There is a digraph corresponding to every square matrix over ℂ. We generate a recurrence relation using the Laplace expansion to calculate the characteristic and the permanent polynomials of a square matrix.
Singh Ranveer, Bapat R. B.
doaj +1 more source
Bounds for the smallest $k$-chromatic graphs of given girth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at least $g$. We consider the problem of determining $n_g(k)$ for small values of $k$ and $g$.
Geoffrey Exoo, Jan Goedgebeur
doaj +1 more source
Open Mathematics, 2018 The problem of structures learning in Bayesian networks is to discover a directed acyclic graph that in some sense is the best representation of the given database. Score-based learning algorithm is one of the important structure learning methods used to
Wang Jingyun, Liu Sanyang
doaj +1 more source