Results 41 to 50 of about 211 (163)

Connected Graph Searching in Outerplanar Graphs

Electronic Notes in Discrete Mathematics, 2005
Search games are a powerfull tool for studying various connectivity parameters of graphs. In the classical search game, we consider an undirected graph G = (V, E) whose edges are initially contaminated. A set of searchers try to clean the graph. At the beginning the graph contains no searchers.
Fedor V. Fomin, Dimitrios M. Thilikos, Ioan Todinca   +2 more
openaire   +1 more source

Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions

Journal of Graph Algorithms and Applications, 2003
This paper investigates the following question: Given a grid ϕ, where ϕ is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at (integral) grid points of ϕ?
Stefan Felsner, Giuseppe Liotta, Stephen Wismath   +2 more
doaj   +1 more source

Fuzzy Outerplanar Graphs and Its Applications

International Journal of Computational Intelligence Systems
The concept of a crisp graph is essential in the study of outerplanar graphs because outerplanar graphs are a unique type of planar graphs containing special characteristics. One of the core concepts of crisp graphs, the notion of a subgraph, is utilized
Deivanai Jaisankar, Sujatha Ramalingam, Nagarajan Deivanayagampillai, Tadesse Walelign   +3 more
doaj   +1 more source

Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems

Journal of Graph Algorithms and Applications, 2007
The task of finding the largest subset of vertices of a graph that induces a planar subgraph is known as the Maximum Induced Planar Subgraph problem (MIPS). In this paper, some new approximation algorithms for MIPS are introduced.
Kerri Morgan, Graham Farr
doaj   +1 more source

Alpha Labeling of Amalgamated Cycles

Theory and Applications of Graphs, 2022
A graceful labeling of a bipartite graph is an \a-labeling if it has the property that the labels assigned to the vertices of one stable set of the graph are smaller than the labels assigned to the vertices of the other stable set.
Christian Barrientos
doaj   +1 more source

On the colorings of outerplanar graphs

Discrete Mathematics, 1995
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire   +1 more source

Monitoring maximal outerplanar graphs [PDF]

Electronic Notes in Discrete Mathematics, 2014
In this paper we define a new concept of monitoring the elements of triangulation graphs by faces. Furthermore, we analyze this, and other monitoring concepts (by vertices and by edges), from a combinatorial point of view, on maximal outerplanar graphs.
Gregorio Hernández-Peñalver, Ana Mafalda Martins   +1 more
openaire   +3 more sources

Toric ideals of matching polytopes and edge colorings

Mathematika, Volume 72, Issue 2, April 2026.
Abstract In this paper, we investigate the maximal degree of minimal generators of the toric ideal of the matching polytope of a graph. It is known that the toric ideal associated with a bipartite graph is generated by binomials of degree at most 3.
Kenta Mori, Ryo Motomura, Hidefumi Ohsugi, Akiyoshi Tsuchiya   +3 more
wiley   +1 more source

Double domination in maximal outerplanar graphs

Open Mathematics, 2022
In graph GG, a vertex dominates itself and its neighbors. A subset S⊆V(G)S\subseteq V\left(G) is said to be a double-dominating set of GG if SS dominates every vertex of GG at least twice.
Zhuang Wei, Zheng Qiuju
doaj   +1 more source

Perfect Matching Under Precedence Constraints

Networks, Volume 87, Issue 2, Page 175-190, March 2026.
ABSTRACT In this article, we motivate and define variants of perfect matching under precedence constraints where a perfect matching is built incrementally and precedence constraints ensure that an edge may only be added to the matching if the edge's predecessor vertices have already been covered.
Christina Büsing, Corinna Mathwieser
wiley   +1 more source