Let G be a finite, simple, and connected graph with the vertex set V and the edge set E. The distance between the vertex u and the edge e=vw is defined as d(u,e)=min{d(u,v),d(u,w)}. A vertex x ...distinguishes two edges e1,e2 if d(x,e1)≠d(x,e2). A subset Le of V is called an edge metric generator for G if every two distinct edges of G are distinguished by some vertex of Le. The minimum cardinality of an edge metric generator for G is called the edge metric dimension and is denoted by dime(G). Similarly, a vertex x distinguishes two elements (vertices or edges) u,v∈V∪E if d(x,u)≠d(x,v). A subset Lm of V is called a mixed metric generator for G if every two distinct elements (vertices and edges) of G are distinguished by some vertex of Lm. The minimum cardinality of a mixed metric generator for G is called the mixed metric dimension and is denoted by dimm(G). In this paper, we study the edge metric dimension and mixed metric dimension of planar graph Qn. We prove that the edge metric dimension and the mixed metric dimension of Qn are both finite and do not depend upon the number of vertices.
The cluster of a crossing in a graph drawing in the plane is the set of the four end-vertices of its two crossed edges. Two crossings are independent if their clusters do not intersect. In this ...paper, we prove that every plane graph with independent crossings has an equitable partition into m induced forests for any m≥8. Moreover, we decrease this lower bound 8 for m to 6, 5, 4 and 3 if we additionally assume that the girth of the considering graph is at least 4, 5, 6 and 26, respectively.
The recursive maximal planar graphs can be obtained from K4, by embedding a 3-vertex in a triangular face continuously. A total k-coloring of a graph G is a coloring of its vertices and edges such ...that no two adjacent or incident elements receive the same color. The Total Coloring Conjecture, in short, TCC, states that every simple graph G is totally (Δ+2)-colorable, where Δ is the maximum degree of G. In this paper, we prove that TCC holds for recursive maximal planar graphs, especially, a main class of recursive maximal planar graphs, named (2,2)-recursive maximal planar graphs, are totally (Δ+1)-colorable. Moreover, we give linear time algorithms for total coloring of recursive maximal planar graphs and (2,2)-recursive maximal planar graphs, respectively.
•Total Coloring Conjecture holds for recursive maximal planar graphs.•(2,2)-recursive maximal planar graphs are totally (Δ + 1)-colorable.•Linear time algorithms are given for total coloring of recursive maximal planar graphs and (2,2)-recursive maximal planar graphs, respectively.
We present a complete analytic solution to the problem of counting planar graphs. We prove an estimate
g
n
∼
g
⋅
n
−
7
/
2
γ
n
n
!
g_n \sim g\cdot n^{-7/2} \gamma ^n n!
for the number
g
n
g_n
of ...labelled planar graphs on
n
n
vertices, where
γ
\gamma
and
g
g
are explicit computable constants. We show that the number of edges in random planar graphs is asymptotically normal with linear mean and variance and, as a consequence, the number of edges is sharply concentrated around its expected value. Moreover we prove an estimate
g
(
q
)
⋅
n
−
4
γ
(
q
)
n
n
!
g(q)\cdot n^{-4}\gamma (q)^n n!
for the number of planar graphs with
n
n
vertices and
⌊
q
n
⌋
\lfloor qn \rfloor
edges, where
γ
(
q
)
\gamma (q)
is an analytic function of
q
q
. We also show that the number of connected components in a random planar graph is distributed asymptotically as a shifted Poisson law
1
+
P
(
ν
)
1+P(\nu )
, where
ν
\nu
is an explicit constant. Additional Gaussian and Poisson limit laws for random planar graphs are derived. The proofs are based on singularity analysis of generating functions and on perturbation of singularities.
The problem of characterizing graphs whose second largest eigenvalue does not exceed a comparatively small constant has attracted a great deal of attention in the last decades. Let T1,2 be the tree ...of diameter 3 with exactly 3 pendent vertices. In this paper, all connected T1,2-free planar graphs whose second largest eigenvalue does not exceed 1 are determined.
For a constant t≥1, a t-spanner of a connected graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. This concept, introduced by ...Peleg and Ullman in 1989, was used in the construction of an optimal synchronizer for the hypercube. We address the problem of finding a t-spanner with minimum number of edges. This problem is called the minimum t-spanner problem (MinSt), and is known to be ▪-hard for every t≥2 even on bounded-degree graphs. Our main contribution is to improve the previous results, by showing that MinSt is ▪-hard even on planar graphs with maximum degree at most 4 (resp. 5) when t≥4 (resp. t=3). We also show that with a slight modification of a result presented by Kobayashi (2018), MinS2 remains ▪-hard on planar graphs with maximum degree 7.
•Minimum t-spanner, for t ≥ 4, on planar graphs G with Δ(G) ≤ 4 is NP-hard.•Minimum 3-spanner on planar graphs G with Δ(G) ≤ 5 is NP-hard.•Minimum 2-spanner on planar graphs G with Δ(G) ≤ 7 is NP-hard.
DP-coloring, which was introduced by Dvořák and Postle, is an extension of list-coloring and DP-chromatic number was studied by many researchers. It is known that some of the proofs which bound ...list-chromatic number also work for DP-coloring. However, it seems difficult to know whether there exists a gap between the list-chromatic number and the DP-chromatic number by only studying the upper bounds of them. In this paper, we examine which types of planar graphs exist when we are given a triple (χ,χℓ,χDP).
A vertex coloring of a graph $G$ is called injective if any two vertices with a common neighbor receive distinct colors. A graph $G$ is injectively $k$-choosable if any list $L$ of admissible colors ...on $V(G)$ of size $k$ allows an injective coloring $\varphi$ such that $\varphi(v)\in L(v)$ whenever $v\in V(G)$. The least $k$ for which $G$ is injectively $k$-choosable is denoted by $\chi_{i}^{l}(G)$. For a planar graph $G$, Bu et al.~proved that $\chi_{i}^{l}(G)\leq\Delta+6$ if girth $g\geq5$ and maximum degree $\Delta(G)\geq8$. In this paper, we improve this result by showing that $\chi_{i}^{l}(G)\leq\Delta+6$ for $g\geq5$ and arbitrary $\Delta(G)$. KCI Citation Count: 0
We prove three conjectures regarding the maximization of spectral invariants over certain families of graphs. Our most difficult result is that the join of P2 and Pn−2 is the unique graph of maximum ...spectral radius over all planar graphs. This was conjectured by Boots and Royle in 1991 and independently by Cao and Vince in 1993. Similarly, we prove a conjecture of Cvetković and Rowlinson from 1990 stating that the unique outerplanar graph of maximum spectral radius is the join of a vertex and Pn−1. Finally, we prove a conjecture of Aouchiche et al. from 2008 stating that a pineapple graph is the unique connected graph maximizing the spectral radius minus the average degree. To prove our theorems, we use the leading eigenvector of a purported extremal graph to deduce structural properties about that graph.
Planar Graphs Have Bounded Queue-Number Dujmović, Vida; Joret, Gwenaël; Micek, Piotr ...
Journal of the ACM,
08/2020, Letnik:
67, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. 66 from 1992. The key to the proof is a new structural tool called
layered partitions
, and the result ...that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number.
Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. 31 that graphs in a proper minor-closed class have low treewidth colourings.
PDF
