Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graphs; trees; central appendage number
graphs; trees; central appendage number
Summary:
The eccentricity of a vertex $v$ of a connected graph $G$ is the distance from $v$ to a vertex farthest from $v$ in $G$. The center of $G$ is the subgraph of $G$ induced by the vertices having minimum eccentricity. For a vertex $v$ in a 2-edge-connected graph $G$, the edge-deleted eccentricity of $v$ is defined to be the maximum eccentricity of $v$ in $G - e$ over all edges $e$ of $G$. The edge-deleted center of $G$ is the subgraph induced by those vertices of $G$ having minimum edge-deleted eccentricity. The edge-deleted central appendage number of a graph $G$ is the minimum difference $|V(H)| - |V(G)|$ over all graphs $H$ where the edge-deleted center of $H$ is isomorphic to $G$. In this paper, we determine the edge-deleted central appendage number of all trees.
References:
[1] Bielak, H.: Minimal realizations of graphs as central subgraphs. Graphs, Hypergraphs, and Matroids. Zágán, Poland (1985), 13-23. MR 0848959 | Zbl 0601.05041
[2] Buckley, F., Miller, Z., Slater, P. J.: On graphs containing a given graph as center. J. Graph Theory 5 (1981), 427-434. DOI 10.1002/jgt.3190050413 | MR 0635706 | Zbl 0449.05056
[3] Koker, J., McDougal, K., Winters, S. J.: The edge-deleted center of a graph. Proceedings of the Eighth Quadrennial Conference on Graph Theory, Combinatorics, Algorithms and Applications. 2 (1998), 567-575. MR 1985087
[4] Koker, J., Moghadam, H., Stalder, S., Winters, S. J.: The edge-deleted central appendage number of graphs. Bull. Inst. Comb. Appl. 34 (2002), 45-54. MR 1880564
[5] Topp, J.: Line graphs of trees as central subgraphs. Graphs, Hypergraphs, and Matroids. Zágán, Poland (1985), 75-83. MR 0848967 | Zbl 0596.05057
Search
Partner of
