Results 81 to 90 of about 231 (167)
On the Planarity of Generalized Line Graphs
Theory and Applications of Graphs, 2019 One of the most familiar derived graphs is the line graph. The line graph $L(G)$ of a graph $G$ is that graph whose vertices are the edges of $G$ where two vertices of $L(G)$ are adjacent if the corresponding edges are adjacent in~$G$.
Khawlah H. Alhulwah +2 more
doaj +1 more source
Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
Journal of Graph Algorithms and Applications, 2013 A graph G = (V,E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each vertex u′ ∈ V corresponds to a leaf u of T and there is an edge (u′, v′) ∈ E if and
Sammi Abida Salma +2 more
doaj +1 more source
Star Coloring Outerplanar Bipartite Graphs
Discussiones Mathematicae Graph Theory, 2019 A proper coloring of the vertices of a graph is called a star coloring if at least three colors are used on every 4-vertex path. We show that all outerplanar bipartite graphs can be star colored using only five colors and construct the smallest known ...
Ramamurthi Radhika, Sanders Gina
doaj +1 more source
Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
Journal of Graph Algorithms and Applications, 2011 Given an embedded planar acyclic digraph G, we define the problem of acyclic hamiltonian path completion with crossing minimization (acyclic-HPCCM) to be the problem of determining a hamiltonian path completion set of edges such that, when these edges ...
Tamara Mchedlidze, Antonios Symvonis
doaj +1 more source
A graph and its complement with specified properties I: connectivity
International Journal of Mathematics and Mathematical Sciences, 1979 We investigate the conditions under which both a graph G and its complement G¯ possess a specified property. In particular, we characterize all graphs G for which G and G¯ both (a) have connectivity one, (b) have line-connectivity one, (c) are 2 ...
Jin Akiyama, Frank Harary
doaj +1 more source
Special Issue Dedicated to the 16th International Symposium on Parameterized and Exact Computation. [PDF]
Algorithmica, 2022 Golovach PA, Zehavi M.
europepmc +1 more source
Subgraph Homeomorphism via the Edge Addition Planarity Algorithm
Journal of Graph Algorithms and Applications, 2012 This paper extends the edge addition planarity algorithm from Boyer and Myrvold to provide a new way of solving the subgraph homeomorphism problem for K2,3, K4, and K3,3.
John Boyer
doaj +1 more source
Indonesian Journal of CombinatoricsA planar graph is said to be zonal when is possible to label its vertices with the nonzero elements of ℤ3, in such a way that the sum of the labels of the vertices on the boundary of each zone is 0 in ℤ3.
Christian Barrientos, Sarah Minion
doaj +1 more source
Non-Preemptive Tree Packing. [PDF]
Algorithmica, 2023 Lendl S, Woeginger G, Wulf L.
europepmc +1 more source