Results 1 to 10 of about 274 (48)
Representing Split Graphs by Words
Discussiones Mathematicae Graph Theory, 2022 There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs.
Chen Herman Z.Q. +2 more
doaj +1 more source
The Crossing Number of Hexagonal Graph H3,n in the Projective Plane
Discussiones Mathematicae Graph Theory, 2022 Thomassen described all (except finitely many) regular tilings of the torus S1 and the Klein bottle N2 into (3,6)-tilings, (4,4)-tilings and (6,3)-tilings.
Wang Jing +3 more
doaj +1 more source
Intersection Dimension and Graph Invariants
Discussiones Mathematicae Graph Theory, 2021 We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δ is at
Aravind N.R., Subramanian C.R.
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
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
The crossing number of the generalized Petersen graph P(3k,k) in the projective plane
AKCE International Journal of Graphs and Combinatorics, 2023 The crossing number of a graph G in a surface Σ, denoted by [Formula: see text], is the minimum number of pairwise intersections of edges in a drawing of G in Σ. Let k be an integer satisfying [Formula: see text], the generalized Petersen graph [Formula:
Jing Wang, Zuozheng Zhang
doaj +1 more source
Minimal Graphs with Respect to Geometric Distance Realizability
Discussiones Mathematicae Graph Theory, 2021 A graph G is minimal non-unit-distance graph if there is no drawing of G in Euclidean plane having all edges of unit length, but, for each edge e of G, G − e has such a drawing.
Madaras Tomáš, Široczki Pavol
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
On characterizing proper max-point-tolerance graphs
AKCE International Journal of Graphs and Combinatorics, 2023 Max-point-tolerance graphs (MPTG) were introduced by Catanzaro et al. in 2017 as a generalization of interval graphs. This graph class has many practical applications in the study of the human genome as well as in signal processing for networks. The same
Sanchita Paul
doaj +1 more source
Annular and pants thrackles [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A thrackle is a drawing of a graph in which each pair of edges meets precisely once. Conway's Thrackle Conjecture asserts that a thrackle drawing of a graph on the plane cannot have more edges than vertices.
Grace Misereh, Yuri Nikolayevsky
doaj +1 more source