Results 41 to 50 of about 4,621 (198)
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
A Note on Edge‐Group Choosability of Planar Graphs without 5‐Cycles
Journal of Mathematics, Volume 2020, Issue 1, 2020., 2020 This paper is devoted to a study of 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. In this paper, we study an edge‐group choosability version of Vizing conjecture for planar graphs without 5‐cycles and for planar graphs without noninduced 5‐cycles (2010 Mathematics ...
Amir Khamseh, Andrei V. Kelarev
wiley +1 more source
Algorithms, 2013 The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry.
Takeyuki Tamura, Tatsuya Akutsu
doaj +1 more source
Nonplanarity of Iterated Line Graphs
Journal of Mathematics, Volume 2020, Issue 1, 2020., 2020 The 1‐crossing index of a graph G is the smallest integer k such that the kth iterated line graph of G has crossing number greater than 1. In this paper, we show that the 1‐crossing index of a graph is either infinite or it is at most 5. Moreover, we give a full characterization of all graphs with respect to their 1‐crossing index.
Jing Wang, Alfred Peris
wiley +1 more source
Pathwidth of outerplanar graphs [PDF]
Journal of Graph Theory, 2006 We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant $c ...
Coudert, David +2 more
openaire +5 more sources
Game Chromatic Number of Generalized Petersen Graphs and Jahangir Graphs
Journal of Applied Mathematics, Volume 2020, Issue 1, 2020., 2020 Let G = (V, E) be a graph, and two players Alice and Bob alternate turns coloring the vertices of the graph G a proper coloring where no two adjacent vertices are signed with the same color. Alice′s goal is to color the set of vertices using the minimum number of colors, which is called game chromatic number and is denoted by χg(G), while Bob′s goal is
Ramy Shaheen +3 more
wiley +1 more source
On the number of series parallel and outerplanar graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g \cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants.
Manuel Bodirsky +3 more
doaj +1 more source
, 2018 Has appeared in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Steven Chaplick +4 more
openaire +4 more sources
Transactions on Combinatorics, 2022 An optimal labeling of a graph with $n$ vertices and $m$ edges is an injective assignment of the first $n$ nonnegative integers to the vertices, that induces, for each edge, a weight given by the sum of the labels of its end-vertices with the ...
Christian Barrientos, Maged Youssef
doaj +1 more source
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles [PDF]
, 2019 Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching ...
Ito, Takehiro +4 more
core +2 more sources