Search · four archives
Search · four archives
22 papers · ranked by Valyu relevance
Noé Demange, Yann Strozecki
We study the problem of connecting the parts of a multipartite graph using a minimum number of edges under a matching constraint. We introduce interconnection trees, defined as matchings whose projections onto the quotient graph form a spanning tree. Motivated by applications in chemoinformatics, we investigate the…
Vesna Iršič Chenoweth, Sandi Klavžar, Gregor Rus, Elif Tan + 1 more
This article discusses mutual-visibility in graphs through a game-based version of the problem. Two players, Builder and Blocker, alternately select an unmarked vertex on a graph keeping the property that the set of marked vertices forms a mutual-visibility set. The game ends when no such selection is possible. The…
Kinkar Chandra Das, Yujun Yang
Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$G=(V, E)$\end{document} G = ( V , E ) be a simple graph. The resistance distance…
Armen R. Davtyan, Gevorg M. Minasyan, Petros A. Petrosyan
An edge-coloring of a graph G with colors 1, . . . , t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an integer interval. It is well-known that there are graphs that do not have interval colorings. The deficiency of a graph G, denoted by…
Colin McDiarmid, Fiona Skerman
It is known that complete graphs and complete multipartite graphs have modularity zero. We show that the least number of edges we may delete from the complete graph Kn to obtain a graph with non-zero modularity is ⌊n/2⌋ + 1. Similarly we determine the least number of edges we may delete from or add to a complete…
David Schaller, Manuel Lafond, Peter F. Stadler, Nicolas Wieseke + 1 more
'Marc Hellmuth'] Several implicit methods to infer horizontal gene transfer (HGT) focus on pairs of genes that have diverged only after the divergence of the two species in which the genes reside. This situation defines the edge set of a graph, the later-divergence-time (LDT) graph, whose vertices correspond to genes…
Charles A. Phillips, Kai Wang, Erich J. Baker, Jason A. Bubier + 2 more
'Elissa J. Chesler' 'Michael A. Langston'] Let k denote an integer greater than 2, let G denote a k-partite graph, and let S denote the set of all maximal k-partite cliques in G. Several open questions concerning the computation of S are resolved. A straightforward and highly-scalable modification to the classic…
Yaser Rowshan, Mostafa Gholami, Stanford Shateyi
The graph $K_{j\timest}$ is a graph which is complete and multipartite which includes j partite sets and t vertices in each partite set. The multipartite Ramsey number (M-R-number) $m_{j}(G_{1},G_{2},…,G_{n})$ is the smallest integer t for the mentioned graphs $G_{1},G_{2},…,G_{n}$, in a way which for each…
József Balogh, Michael C. Wigal
Let r ≥ 3 be fixed and G be an n-vertex graph. A long-standing conjecture of Gy˝ori states that if e(G) = tr−1(n) + k, where tr−1(n) denotes the number of edges of the Tur´an graph on n vertices and r − 1 parts, then G has at least (2 − o(1))k/r edge disjoint r-cliques. We prove this conjecture.
Jesús Gómez-Gardeñes, Ernesto Estrada
We define the anti-communicability function for the nodes of a simple graph as the nondiagonal entries of exp (−A). We prove that it induces an embedding of the nodes into a Euclidean space. The anti-communicability angle is then defined as the angle spanned by the position vectors of the corresponding nodes in the…
Oleg Pikhurko, Katherine Staden, Zelealem B. Yilma
Let k := (k1, . . . , ks) be a sequence of natural numbers. For a graph G, let F(G; k) denote the number of colourings of the edges of G with colours 1, . . . , s such that, for every c ∈ {1, . . . , s}, the edges of colour c contain no clique of order kc. Write F(n; k) to denote the maximum of F(G; k) over all graphs…
Jørgen Bang‐Jensen, Yun Wang, Anders Yeo
A digraph is semicomplete if it has no pair of non-adjacent vertices. It is complete if every pair of distinct vertices induce a 2-cycle. It is well-known and easy to show that even the following version of the directed travelling salesman problem is NP-complete: Given a strongly connected complete digraph D = (V, A)…
Thijs van Veluw
We study equality in the Hoffman bound for the chromatic number and Hoffman colorings in regular and irregular graphs. We investigate the connection between Hoffman colorability and several graph operations, of which the tensor product is especially interesting in this context. We then introduce the Decomposition…
Authors not listed
Genetic Algorithms are a powerful method to solve optimization problems with complex cost functions over vast search spaces that rely in particular on recombining parts of previous solutions. Crossover operators play a crucial role in this context. Here, we describe a large class of these operators designed for…
Paolo Boldi, Chiara Prezioso, Flavio Furia, Ian Stewart + 1 more
Axiomatizing centrality measures often requires proving that certain properties do not hold by exhibiting a counterexample (i.e., a graph for which a given centrality measure does not satisfy a specified property). In the context of geometric centralities, constructing such counterexamples requires building a graph…
Benedict Paten, Adam M Novak, Erik Garrison, Glenn Hickey
A superbubble is a type of directed acyclic subgraph with single distinct source and sink vertices. In genome assembly and genetics, the possible paths through a superbubble can be considered to represent the set of possible sequences at a location in a genome. Bidirected and biedged graphs are a generalization of…
Authors not listed
SynTemp is a framework designed to extract and hierarchically cluster reaction templates from large-scale reaction data repositories. Reaction templates are partial Imaginary Transition State graphs representing the reaction center as well as surrounding context. These graphs are equivalent to Double Pushout graph…
César A.D. Xavier, Márcio T. Godinho, Talita B. Mar, Camila G. Ferro + 8 more
Several key evolutionary events marked the evolution of geminiviruses, culminating with the emergence of bipartite genomes represented by viruses classified in the genus Begomovirus. This genus represents the most abundant group of multipartite viruses, contributing significantly to the observed abundance of…
Erick Bermúdez-Méndez, Kirsten F. Bronsvoort, Mark P. Zwart, Sandra van de Water + 6 more
Bunyaviruses lack a specific mechanism to ensure the incorporation of a complete set of genome segments into each virion, explaining the generation of incomplete virus particles lacking one or more genome segments. Such incomplete virus particles, which may represent the majority of particles produced, are generally…
Laura Eslava, Sayle Sigarreta Ricardo, Arno Siri-Jégousse
We prove that the generalized Randić index over graphs following the Erdos-Rényi model, for both the sparse and dense regimes, is concentrated around its mean when the number of vertices tends to infinity.
Authors not listed
Previously we posited that a systematic and general description of stereoisomerism could be based upon the principles of the polytopal rearrangement model. The most daunting challenge to this end is to comprehensively describe all possible geometries for arbitrary n-coordinate centres, ABn, and for this we have…
Marc Hellmuth, Annachiara Korchmaros, José Antonio Ramírez-Rafael, Bruno Schmidt + 2 more
Horizontal gene transfer is an important contributor to evolution. Following Walter M. Fitch, two genes are xenologs if at least one HGT separates them. More formally, the directed Fitch graph has a set of genes as its vertices, and directed edges (x, y) for all pairs of genes x and y for which y has been horizontally…