The Firefighter problem with dynamic defence costs. [PDF]
PLoS OneHunter E, Enright J.
europepmc +1 more source
The Strong Nash‐Williams Orientation Theorem for Rayless Graphs
Journal of Graph Theory, EarlyView.ABSTRACT In 1960, Nash‐Williams proved his strong orientation theorem that every finite graph has an orientation in which the number of arc‐disjoint directed paths between any two vertices is at least half the number of undirected edge‐disjoint paths between them (rounded down).
Max Pitz, Jacob Stegemann
wiley +1 more source
Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation. [PDF]
Algorithms Mol BiolUrata T +3 more
europepmc +1 more source
Path Degeneracy and Applications
Journal of Graph Theory, EarlyView.ABSTRACT In this work, we relate girth and path‐degeneracy in classes with sub‐exponential expansion, with explicit bounds for classes with polynomial expansion and proper minor‐closed classes that are tight up to a constant factor (and tight up to second order terms if a classical conjecture on existence of g $g$‐cages is verified). As an application,
Yuquan Lin, Patrice Ossona de Mendez
wiley +1 more source
Moonshine.jl: a Julia package for genome-scale model-based ancestral recombination graph inference. [PDF]
Front GenetFournier P, Larribe F.
europepmc +1 more source
Line Graphs of Multigraphs and the Forbidden Graph E 6
Journal of Graph Theory, EarlyView.ABSTRACT The line graph Γ of a multigraph Δ is the graph whose vertices are the edges of Δ, where two such edges are adjacent if and only if they meet in a single vertex of Δ. We provide several characterizations of such line graphs and in particular show that a graph is a line graph if and only if it does not contain one of the 32 graphs, all of which
Hans Cuypers
wiley +1 more source
Investigating topological indices and entropy measures for titanium diboride network. [PDF]
Discov NanoSaher R +4 more
europepmc +1 more source
On Sparsity Conditions Guaranteeing a Fractional Coloring
Journal of Graph Theory, EarlyView.ABSTRACT A graph has an ( a : b ) $(a:b)$ ‐coloring if there exists an assignment from the vertices to subsets of { 1 , … , a } $\{1,\ldots ,a\}$ with size b $b$ such that adjacent vertices are assigned disjoint subsets. Odd girth at least 2 k + 1 $2k+1$ is a necessary condition for a graph to have a ( 2 k + 1 : k ) $(2k+1:k)$‐coloring.
Ilkyoo Choi
wiley +1 more source
Decomposable and Essentially Univariate Mass-Action Systems: Extensions of the Deficiency One Theorem. [PDF]
J Nonlinear SciDeshpande A, Müller S.
europepmc +1 more source
Saturated Partial Embeddings of Planar Graphs
Journal of Graph Theory, EarlyView.ABSTRACT In this work, we study how far one can deviate from optimal behavior when embedding a planar graph. For a planar graph G $G$, we say that a plane subgraph H ⊆ G $H\subseteq G$ is a plane‐saturated subgraph if adding any edge (possibly with new vertices) to H $H$ would either violate planarity or make the resulting graph no longer a subgraph of
Alexander Clifton, Nika Salia
wiley +1 more source