Results 1 to 10 of about 1,967 (126)
Sombor characteristic values of cographs. [PDF]
HeliyonA unique class of cograph is examined, that is defined recursively as C=C(n1)=K‾n1, and C=C(n1,n2,…,ni)=C(n1,n2,…,ni−1)∪Kni‾, for 2≤i≤k. The Sombor spectrum of C is calculated, the Sombor spectral radius and establish the sharp bounds for the Sombor ...
Raza Z, Rather BA, Imran M.
europepmc +4 more sources
Defective Coloring on Classes of Perfect Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 In Defective Coloring we are given a graph $G$ and two integers $\chi_d$, $\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximum degree induced by any color class is at most $\Delta^*$.
Rémy Belmonte +2 more
doaj +3 more sources
Relative timing information and orthology in evolutionary scenarios. [PDF]
Algorithms Mol Biol, 2023 Background Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree T to vertices and edges of a species tree S.
Schaller D +5 more
europepmc +2 more sources
Monadic second-order definable graph orderings [PDF]
Logical Methods in Computer Science, 2014 We study the question of whether, for a given class of finite graphs, one can define, for each graph of the class, a linear ordering in monadic second-order logic, possibly with the help of monadic parameters.
Achim Blumensath, Bruno Courcelle
doaj +5 more sources
Orthology and near-cographs in the context of phylogenetic networks. [PDF]
Algorithms Mol BiolOrthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of orthology estimates without prior knowledge of the underlying gene or ...
Lindeberg A +3 more
europepmc +2 more sources
An Analytic Propositional Proof System on Graphs [PDF]
Logical Methods in Computer Science, 2022 In this paper we present a proof system that operates on graphs instead of formulas. Starting from the well-known relationship between formulas and cographs, we drop the cograph-conditions and look at arbitrary undirected) graphs. This means that we lose
Matteo Acclavio +2 more
doaj +1 more source
Induced betweenness in order-theoretic trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure.
Bruno Courcelle
doaj +1 more source
Tuza's Conjecture for Threshold Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including
Marthe Bonamy +6 more
doaj +1 more source
A System of Interaction and Structure III: The Complexity of BV and Pomset Logic [PDF]
Logical Methods in Computer Science, 2023 Pomset logic and BV are both logics that extend multiplicative linear logic (with Mix) with a third connective that is self-dual and non-commutative. Whereas pomset logic originates from the study of coherence spaces and proof nets, BV originates from ...
Lê Thành Dũng Nguyên +1 more
doaj +1 more source
Sum structures in abelian groups
Examples and Counterexamples, 2023 Any set S of elements from an abelian group produces a graph with colored edges G(S), with its points the elements of S, and the edge between points P and Q assigned for its “color” the sum P+Q.
Robert Haas
doaj +1 more source