ALMOST-PERIPHERAL GRAPHS
| Autor: | S. B. Lokesh, Sandi Klavžar, Kishori P. Narayankar, H. B. Walikar |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
General Mathematics Symmetric graph ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS Voltage graph self-centered graph Distance-regular graph almost-peripheral graph law.invention Combinatorics Vertex-transitive graph 90B80 Graph power law Line graph 05C75 diameter 05C12 radius Complement graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics Distance-hereditary graph |
| Zdroj: | Taiwanese J. Math. 18, no. 2 (2014), 463-471 |
| ISSN: | 1027-5487 |
| DOI: | 10.11650/tjm.18.2014.3267 |
| Popis: | The center $C(G)$ and the periphery $P(G)$ of a connected graph $G$ consist of the vertices of minimum and maximum eccentricity, respectively. Almost-peripheral (AP) graphs are introduced as graphs $G$ with $|P(G)| = |V(G)| - 1$ (and $|C(G)| = 1$). AP graph of radius $r$ is called an $r$-AP graph. Several constructions of AP graph are given, in particular implying that for any $r\ge 1$, any graph can be embedded as an induced subgraph into some $r$-AP graph. A decomposition of AP-graphs that contain cut-vertices is presented. The $r$-embedding index $\Phi_{r}(G)$ of a graph $G$ is introduced as the minimum number of vertices which have to be added to $G$ such that the obtained graph is an $r$-AP graph. It is proved that $\Phi_{2}(G)\le 5$ holds for any non-trivial graphs and that equality holds if and only if $G$ is a complete graph. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|