N_ 2-locally disconnected graphs

DOI10.1016/0012-365X(93)90551-4MaRDI QIDQ1309470zbMATH OpenWikidataFDO

Authors Zdeněk Ryjáček

Publication date 25 April 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90551-4

zbMATH Keywords

\(N_ 2\)-locally disconnected graphs bound planar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Graph theory (05C99)

Review text

A new type of neighbourhood of a vertex in a graph is introduced. An edge \(yz\) of an undirected graph \(G\) is called adjacent to a vertex \(x\), if \(y \neq x \neq z\) and at least one of the vertices \(y\), \(z\) is adjacent to \(x\). The neighbourhood of the second type of \(x\) is the edge-induced subgraph of \(G\) on the edges that are adjacent to \(x\); it is denoted by \(N_ 2(x,G)\). If \(N_ 2(x,G)\) is disconnected for each vertex \(x\) of \(G\), then \(G\) is called \(N_ 2\)-locally disconnected. For \(n\geq 5\), by \(t(n)\) (or \(t_ p(n))\) the maximum number of edges of an \(N_ 2\)- locally disconnected (or planar \(N_ 2\)-locally disconnected, respectively) graph with \(n\) vertices is denoted. Exact values of \(t_ p(n)\) are found for all \(n \geq 5\). For \(t(n)\) both the lower bound and the upper bound are determined.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: \(N_ 2\)-locally disconnected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1309470)