Results 151 to 160 of about 5,057 (262)

Disjoint Total Dominating Sets in Planar Graphs

Journal of Graph Theory, Volume 112, Issue 3, Page 290-295, July 2026.
ABSTRACT The vertex set of any planar graph of minimum degree at least 3 can be colored in two colors so that every vertex has a neighbor of each color. If the graph is a planar triangulation, the coloring can be chosen such that every vertex has a neighbor of its own color and at least two neighbors of the opposite color.
Eva Rotenberg, Daniel Rutschmann, Carsten Thomassen   +2 more
wiley   +1 more source

Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below

Forum of Mathematics, Sigma
The smallest eigenvalue of a graph is the smallest eigenvalue of its adjacency matrix. We show that the family of graphs with smallest eigenvalue at least $-\lambda $ can be defined by a finite set of forbidden induced subgraphs if and only if
Zilin Jiang, Alexandr Polyanskii
doaj   +1 more source

Sensitivity and Hamming Graphs

Journal of Graph Theory, Volume 112, Issue 3, Page 296-305, July 2026.
ABSTRACT For any m ≥ 3 we show that the Hamming graph H ( n , m ) admits an imbalanced partition into m sets, each inducing a subgraph of low maximum degree. This improves previous results by Tandya and by Potechin and Tsang, and disproves the Strong m‐ary Sensitivity Conjecture of Asensio, García‐Marco, and Knauer.
Sara Asensio, Yuval Filmus, Ignacio García‐Marco, Kolja Knauer   +3 more
wiley   +1 more source

Path Eccentricity and Forbidden Induced Subgraphs

CoRR
Abstract.
Cichacz, Sylwia, Hilaire, Claire, Masařík, Tomáš, Masaříková, Jana, Milanič, Martin   +4 more
openaire   +3 more sources

Treewidth Versus Clique Number. V. Further Connections With Tree‐Independence Number

Journal of Graph Theory, Volume 112, Issue 3, Page 337-351, July 2026.
ABSTRACT We continue the study of ( tw , ω )‐bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel ...
Claire Hilaire, Martin Milanič, Ðorđe Vasić   +2 more
wiley   +1 more source

Forbidden induced subgraphs for threshold-like graph classes

, 2019
Every hereditary graph class (closed under induced subgraphs) has a characterization by forbidden induced subgraphs: graphs not in the class but every graph obtained by deleting a vertex is in the class.
Sivaraman, Vaidyanathan
core  

Ordered Median Traveling Salesman Problem

Networks, Volume 88, Issue 1, Page 59-84, July 2026.
ABSTRACT This paper introduces a novel combinatorial optimization problem with ordering constraints, termed the Ordered Median Traveling Salesman Problem (OMTSP). The OMTSP integrates key elements from both the classic Traveling Salesman Problem (TSP) and the Ordered Median Location Problem.
Ivana Ljubić, Alfredo Marín, Justo Puerto, Francisco Temprano   +3 more
wiley   +1 more source

Large Deviations of the Giant Component in Scale‐Free Inhomogeneous Random Graphs

Random Structures &Algorithms, Volume 68, Issue 4, July 2026.
ABSTRACT We study large deviations of the size of the largest connected component in a general class of inhomogeneous random graphs with iid weights, parametrized so that the degree distribution is regularly varying. We derive a large‐deviation principle with logarithmic speed: the rare event that the largest component contains linearly more vertices ...
Joost Jorritsma, Bert Zwart
wiley   +1 more source

Is It Easier to Count Communities Than Find Them?

Random Structures &Algorithms, Volume 68, Issue 4, July 2026.
ABSTRACT Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: Might it be possible to infer properties of the community
Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang   +3 more
wiley   +1 more source

Inter‐platform ecosystems

Strategic Management Journal, Volume 47, Issue 7, Page 1840-1877, July 2026.
Abstract Research Summary We extend ecosystem theory to cases in which platforms are complementors to each other: inter‐platform ecosystems. Analyzing web traffic data on 241 European platforms, we identify and characterize demand‐side inter‐platform ecosystems, and propose a theory of why they emerge.
Bruno Carballa‐Smichowski, Néstor Duch‐Brown, Bertin Martens, Álvaro Gomez‐Losada   +3 more
wiley   +1 more source