Results 51 to 60 of about 1,010 (104)
Flippable Edges in Triangulations on Surfaces
Discussiones Mathematicae Graph Theory, 2022 Concerning diagonal flips on triangulations, Gao et al. showed that any triangulation G on the sphere with n ≥ 5 vertices has at least n − 2 flippable edges.
Ikegami Daiki, Nakamoto Atsuhiro
doaj +1 more source
On An Extremal Problem In The Class Of Bipartite 1-Planar Graphs
Discussiones Mathematicae Graph Theory, 2016 A graph G = (V, E) is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. In this paper, we study bipartite 1-planar graphs with prescribed numbers of vertices in partite sets.
Czap Július +2 more
doaj +1 more source
Split Euler Tours In 4-Regular Planar Graphs
Discussiones Mathematicae Graph Theory, 2016 The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split ...
Couch PJ +3 more
doaj +1 more source
k-forested choosability of graphs with bounded maximum average degree [PDF]
, 2011 A proper vertex coloring of a simple graph is $k$-forested if the graph induced by the vertices of any two color classes is a forest with maximum degree less than $k$.
Communicated Hossein Hajiabolhassan +3 more
core
Light Graphs In Planar Graphs Of Large Girth
Discussiones Mathematicae Graph Theory, 2016 A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢).
Hudák Peter +3 more
doaj +1 more source
On Independent Domination in Planar Cubic Graphs
Discussiones Mathematicae Graph Theory, 2019 A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S.
Abrishami Gholamreza +2 more
doaj +1 more source
The Crossing Number of Join of the Generalized Petersen Graph P(3, 1) with Path and Cycle
Discussiones Mathematicae Graph Theory, 2018 There are only few results concerning the crossing numbers of join of some graphs. In this paper, the crossing numbers of join products for the generalized Petersen graph P(3, 1) with n isolated vertices as well as with the path Pn on n vertices and with
Ouyang Zhang Dong +2 more
doaj +1 more source
The Crossing Number of The Hexagonal Graph H3,n
Discussiones Mathematicae Graph Theory, 2019 In [C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323 (1991) 605–635], Thomassen described completely all (except finitely many) regular tilings of the torus S1 and the ...
Wang Jing +2 more
doaj +1 more source
A Note on the Crossing Numbers of 5-Regular Graphs
Discussiones Mathematicae Graph Theory, 2020 The crossing number cr(G) of a graph G is the smallest number of edge crossings in any drawing of G. In this paper, we prove that there exists a unique 5-regular graph G on 10 vertices with cr(G) = 2.
Ouyang Zhangdong
doaj +1 more source
The Thickness of Amalgamations and Cartesian Product of Graphs
Discussiones Mathematicae Graph Theory, 2017 The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is a measurement of the closeness to the planarity of a graph, and it also has important applications to VLSI design, but it has been ...
Yang Yan, Chen Yichao
doaj +1 more source