Results 11 to 20 of about 132 (112)
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
Regularity and Planarity of Token Graphs
Discussiones Mathematicae Graph Theory, 2017 Let G = (V, E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G.
Carballosa Walter +3 more
doaj +1 more source
Additive List Coloring of Planar Graphs with Given Girth
Discussiones Mathematicae Graph Theory, 2020 An additive coloring of a graph G is a labeling of the vertices of G from {1, 2, . . . , k} such that two adjacent vertices have distinct sums of labels on their neighbors.
Brandt Axel +2 more
doaj +1 more source
The Planar Index and Outerplanar Index of Some Graphs Associated to Commutative Rings
Discussiones Mathematicae - General Algebra and Applications, 2019 In this paper, we study the planar and outerplanar indices of some graphs associated to a commutative ring. We give a full characterization of these graphs with respect to their planar and outerplanar indices when R is a finite ring.
Barati Zahra, Afkhami Mojgan
doaj +1 more source
On the planarity of line Mycielskian graph of a graph
Ratio Mathematica, 2020 The line Mycielskian graph of a graph G, denoted by Lμ(G) is defined as the graph obtained from L(G) by adding q+1 new vertices E' = ei' : 1 ≤ i ≤ q and e, then for 1 ≤ i ≤ q , joining ei' to the neighbours of ei and to e.
Keerthi G. Mirajkar +1 more
doaj +1 more source
A Survey on the Cyclic Coloring and its Relaxations
Discussiones Mathematicae Graph Theory, 2021 A cyclic coloring of a plane graph is a vertex coloring such that any two vertices incident with the same face receive distinct colors. This type of coloring was introduced more than fifty years ago, and a lot of research in chromatic graph theory was ...
Czap Július +2 more
doaj +1 more source
Long-Scale Ollivier Ricci Curvature of Graphs
Analysis and Geometry in Metric Spaces, 2019 We study the long-scale Ollivier Ricci curvature of graphs as a function of the chosen idleness. Similarly to the previous work on the short-scale case, we show that this idleness function is concave and piecewise linear with at most 3 linear parts.
Cushing D., Kamtue S.
doaj +1 more source
Coverings of Cubic Graphs and 3-Edge Colorability
Discussiones Mathematicae Graph Theory, 2021 Let h:G˜→Gh:\tilde G \to G be a finite covering of 2-connected cubic (multi)graphs where G is 3-edge uncolorable. In this paper, we describe conditions under which G˜\tilde G is 3-edge uncolorable. As particular cases, we have constructed regular and
Plachta Leonid
doaj +1 more source
The Crossing Number of Cartesian Product of 5-Wheel with any Tree
Discussiones Mathematicae Graph Theory, 2021 In this paper, we establish the crossing number of join product of 5-wheel with n isolated vertices. In addition, the exact values for the crossing numbers of Cartesian products of the wheels of order at most five with any tree T are given.
Wang Yuxi, Huang Yuanqiu
doaj +1 more source
A subexponential construction of graph coloring for multiparty computation
Journal of Mathematical Cryptology, 2014 We show the first deterministic construction of an unconditionally secure multiparty computation (MPC) protocol in the passive adversarial model over black-box non-Abelian groups which is both optimal (secure against an adversary who possesses any ...
Asghar Hassan Jameel +3 more
doaj +1 more source