Results 11 to 20 of about 131 (107)
A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs [PDF]
Discussiones Mathematicae Graph Theory, 2017 We characterize the class L32$L_3^2 $ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs.
Metelsky Yury +2 more
doaj +2 more sources
Even circuits in oriented matroids [PDF]
, 2022 In this paper we generalise the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids.
Heuer, Karl +2 more
core +1 more source
Disjoint dijoins for classes of dicuts in finite and infinite digraphs [PDF]
, 2022 A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of a set of edges meeting every non-empty dicut equals ...
Heuer, Karl +3 more
core +1 more source
Strong Geodetic Problem in Networks
Discussiones Mathematicae Graph Theory, 2020 In order to model certain social network problems, the strong geodetic problem and its related invariant, the strong geodetic number, are introduced.
Manuel Paul +4 more
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2020 If S = (a1, a2, . . .) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1, X2, . . .
Brešar Boštjan +3 more
doaj +1 more source
Minimally Strong Subgraph (k,ℓ)-Arc-Connected Digraphs
Discussiones Mathematicae Graph Theory, 2022 Let D = (V,A) be a digraph of order n, S a subset of V of size k and 2 ≤ k ≤ n. A subdigraph H of D is called an S-strong subgraph if H is strong and S ⊆ V (H). Two S-strong subgraphs D1 and D2 are said to be arc-disjoint if A(D1) ∩ A(D2) = ∅.
Sun Yuefang, Jin Zemin
doaj +1 more source
Decomposing tournaments into paths
Proceedings of the London Mathematical Society, Volume 121, Issue 2, Page 426-461, August 2020., 2020 Abstract We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kühn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number
Allan Lo +3 more
wiley +1 more source
Eigenvalue bracketing for discrete and metric graphs [PDF]
, 2008 28 pages, 6 figures.-- MSC2000 codes: 05C50, 05C70, 47A10.-- ArXiv pre-print available at: http://arxiv.org/abs/0804.1076MR#: MR2446037 (2010a:47076)Zbl#: Zbl 1152.05044We develop eigenvalue estimates for the Laplacians on discrete and metric graphs ...
Post, Olaf +4 more
core +1 more source
A note on flow polynomials of graphs [PDF]
, 2008 R. China Using the decomposition theory of modular and integral flow polynomials, we answer a problem of Beck and Zaslavsky, by providing a general situation in which the integral flow polynomial is a multiple of the modular flow polynomial.
Arthur L. B. Yang +3 more
core +1 more source
On the Number of Disjoint 4-Cycles in Regular Tournaments
Discussiones Mathematicae Graph Theory, 2018 In this paper, we prove that for an integer r ≥ 1, every regular tournament T of degree 3r − 1 contains at least 2116r-103${{21} \over {16}}r - {{10} \over 3}$ disjoint directed 4-cycles. Our result is an improvement of Lichiardopol’s theorem when taking
Ma Fuhong, Yan Jin
doaj +1 more source