Results 81 to 90 of about 4,003 (201)
On the chromatic index of outerplanar graphs
Journal of Combinatorial Theory, Series B, 1975 AbstractVizing [Diskret. Analiz 3 (1964), 25–30] has shown that if ϱ denotes the maximum valency of a simple graph, then its chromatic index is either ϱ or ϱ + 1. The object of this paper is to show that the chromatic index of an outerplanar graph G is ϱ if and only if G is not an odd circuit.
openaire +3 more sources
Random graphs embeddable in order‐dependent surfaces
Random Structures &Algorithms, Volume 64, Issue 4, Page 940-985, July 2024.Abstract Given a ‘genus function’ g=g(n)$$ g=g(n) $$, we let Eg$$ {\mathcal{E}}^g $$ be the class of all graphs G$$ G $$ such that if G$$ G $$ has order n$$ n $$ (i.e., has n$$ n $$ vertices) then it is embeddable in a surface of Euler genus at most g(n)$$ g(n) $$.
Colin McDiarmid, Sophia Saller
wiley +1 more source
A note on zero-divisor graph of amalgamated duplication of a ring along an ideal
AKCE International Journal of Graphs and Combinatorics, 2017 Let be a commutative ring and be a non-zero ideal of . Let be the subring of consisting of the elements for and . In this paper we characterize all isomorphism classes of finite commutative rings with identity and ideal such that is planar.
A. Mallika, R. Kala
doaj +1 more source
Frequent subgraph mining in outerplanar graphs [PDF]
Data Mining and Knowledge Discovery, 2006 In recent years there has been an increased interest in algorithms that can perform frequent pattern discovery in large databases of graph structured objects. While the frequent connected subgraph mining problem for tree datasets can be solved in incremental polynomial time, it becomes intractable for arbitrary graph databases. Existing approaches have
Horvath +3 more
openaire +5 more sources
On tree decompositions whose trees are minors
Journal of Graph Theory, Volume 106, Issue 2, Page 296-306, June 2024.Abstract In 2019, Dvořák asked whether every connected graph G $G$ has a tree decomposition ( T , B ) $(T,{\rm{ {\mathcal B} }})$ so that T $T$ is a subgraph of G $G$ and the width of ( T , B ) $(T,{\rm{ {\mathcal B} }})$ is bounded by a function of the treewidth of G $G$.
Pablo Blanco +5 more
wiley +1 more source
On edge-group choosability of graphs [PDF]
, 2011 In this paper, we study the concept of edge-group choosability of graphs. We say that G is edge k-group choosable if its line graph is k-group choosable. An edge-group choosability version of Vizing conjecture is given.
Khamseh, Amir, Omidi, Gholamreza
core
A node-capacitated Okamura-Seymour theorem
, 2012 The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are ...
Lee, James R. +2 more
core +1 more source
Drawing outerplanar graphs using three edge lengths
Computational Geometry, 2015 It is shown that for any outerplanar graph G there is a one to one mapping of the vertices of G to the plane, so that the number of distinct distances between pairs of connected vertices is at most three. This settles a problem of Carmi, Dujmovic, Morin and Wood.
Ohad N. Feldheim, Noga Alon
openaire +4 more sources
The product structure of squaregraphs
Journal of Graph Theory, Volume 105, Issue 2, Page 179-191, February 2024.Abstract A squaregraph is a plane graph in which each internal face is a 4‐cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path.
Robert Hickingbotham +3 more
wiley +1 more source
Crosscap of the non-cyclic graph of groups
AKCE International Journal of Graphs and Combinatorics, 2016 The non-cyclic graph CG to a non locally cyclic group G is as follows: take G∖Cyc(G) as vertex set, where Cyc(G)={x∈G|〈x,y〉 is cyclic for all y∈G} is called the cyclicizer of G, and join two vertices if they do not generate a cyclic subgroup.
K. Selvakumar, M. Subajini
doaj +1 more source