Results 11 to 20 of about 107 (87)
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
On Antipodal and Diametrical Partial Cubes
Discussiones Mathematicae Graph Theory, 2021 We prove that any diametrical partial cube of diameter at most 6 is antipodal. Because any antipodal graph is harmonic, this gives a partial answer to a question of Fukuda and Handa [Antipodal graphs and oriented matroids, Discrete Math.
Polat Norbert
doaj +1 more source
A Constructive Characterization of Vertex Cover Roman Trees
Discussiones Mathematicae Graph Theory, 2021 A Roman dominating function on a graph G = (V (G), E(G)) is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2.
Martínez Abel Cabrera +2 more
doaj +1 more source
Dualizing Distance-Hereditary Graphs
Discussiones Mathematicae Graph Theory, 2021 Distance-hereditary graphs can be characterized by every cycle of length at least 5 having crossing chords. This makes distance-hereditary graphs susceptible to dualizing, using the common extension of geometric face/vertex planar graph duality to cycle ...
McKee Terry A.
doaj +1 more source
Capture-Time Extremal Cop-Win Graphs
Discussiones Mathematicae Graph Theory, 2021 We investigate extremal graphs related to the game of Cops and Robbers. We focus on graphs where a single cop can catch the robber; such graphs are called cop-win.
Offner David, Ojakian Kerry
doaj +1 more source
Covering the Edges of a Random Hypergraph by Cliques
Discussiones Mathematicae Graph Theory, 2022 We determine the order of magnitude of the minimum clique cover of the edges of a binomial, r-uniform, random hypergraph G(r)(n, p), p fixed. In doing so, we combine the ideas from the proofs of the graph case (r = 2) in Frieze and Reed [Covering the ...
Rödl Vojtěch, Ruciński Andrzej
doaj +1 more source
A Spectral Characterization of the S-Clique Extension of the Triangular Graphs
Discussiones Mathematicae Graph Theory, 2020 A regular graph is co-edge regular if there exists a constant µ such that any two distinct and non-adjacent vertices have exactly µ common neighbors. In this paper, we show that for integers s ≥ 2 and n large enough, any co-edge-regular graph which is ...
Tan Ying-Ying +2 more
doaj +1 more source
On Proper (Strong) Rainbow Connection of Graphs
Discussiones Mathematicae Graph Theory, 2021 A path in an edge-colored graph G is called a rainbow path if no two edges on the path have the same color. The graph G is called rainbow connected if between every pair of distinct vertices of G, there is a rainbow path.
Jiang Hui +3 more
doaj +1 more source
On the 12-Representability of Induced Subgraphs of a Grid Graph
Discussiones Mathematicae Graph Theory, 2022 The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53].
Chen Joanna N., Kitaev Sergey
doaj +1 more source