Results 1 to 10 of about 27,884 (262)
Fast simulation of planar Clifford circuits [PDF]
QuantumA general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally ...
David Gosset +3 more
doaj +1 more source
Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs
Discussiones Mathematicae Graph Theory, 2020 Two distinct crossings are independent if the end-vertices of the crossed pair of edges are mutually different. If a graph G has a drawing in the plane such that every two crossings are independent, then we call G a plane graph with independent crossings
Song Wen-Yao +2 more
doaj +1 more source
On the Synthesis of Planar Graphs with Given Properties
Кібернетика та комп'ютерні технологіїThe problem of studying the structural properties of planar subgraphs G\v, where v is an arbitrary vertex of a graph G of undirected genus, is considered, using cell chains that connect limit cycles with points of a given set M of the graph G\v.
Volodymyr Petrenjuk, Dmytro Petreniuk
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
$1$-string $B_2$-VPG representation of planar graphs
Journal of Computational Geometry, 2016 In this paper, we prove that every planar graph has a 1-string $B_2$-VPG representation—a string representation using paths in a rectangular grid that contain at most two bends.
Therese Biedl, Martin Derka
doaj +1 more source
A note on the coprime graph of a group [PDF]
International Journal of Group Theory, 2016 In this paper we study the coprime graph of a group $G$. The coprime graph of a group $G$, is a graph whose vertices are elements of $G$ and two distinct vertices $x$ and $y$ are adjacent iff $(|x|,|y|)=1$.
Hamid Reza Dorbidi
doaj
On-line coloring of $I_s$-free graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 An on-line vertex coloring algorithm receives vertices of a graph in some externally determined order. Each new vertex is presented together with a set of the edges connecting it to the previously presented vertices.
Iwona Cieslik, Marcin Kozik, Piotr Micek
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
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
Strong oriented chromatic number of planar graphs without short cycles
Discrete Mathematics & Theoretical Computer Science, 2008 Let M be an additive abelian group. A strong oriented coloringof an oriented graph G is a mapping φ from V(G) to M such that (1) φ(u) ≠ φ(v) whenever uv is an arc in G and (2) φ(v) - φ(u) ≠ -(φ(t) - φ(z)) whenever uv and zt are two arcs in
Mickaël Montassier +2 more
doaj