Cut and pendant vertices and the number of connected induced subgraphs of a graph

DOI10.1007/S40879-020-00443-8MaRDI QIDQ2040982zbMATH OpenOpenAlexFDO

Authors Audace A. V. Dossou-Olory

Publication date 15 July 2021

Published in European Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.04552

zbMATH Keywords

treeconnected graphinduced subgraphpendant vertexcut vertexextremal graph structure

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Connectivity (05C40)

Abstract: A vertex whose removal in a graph $G$ increases the number of components of $G$ is called a cut vertex. For all $n,c$, we determine the maximum number of connected induced subgraphs in a connected graph with order $n$ and $c$ cut vertices, and also characterise those graphs attaining the bound. Moreover, we show that the cycle has the smallest number of connected induced subgraphs among all cut vertex-free connected graphs. The general case $c>0$ remains an open task. We also characterise the extremal graph structures given both order and number of pendant vertices, and establish the corresponding formulas for the number of connected induced subgraphs. The `minimal' graph in this case is a tree, thus coincides with the structure that was given by Li and Wang~[Further analysis on the total number of subtrees of trees. emph{Electron. J. Comb.} 19(4), #P48, 2012].

Recommendations

• Maximising the number of connected induced subgraphs of unicyclic graphs
• The number of subtrees in graphs with given number of cut edges
• On the number of cut-vertices in a graph
• scientific article; zbMATH DE number 7714103
• The number of cutvertices in graphs with given minimum degree

Cites work

• scientific article; zbMATH DE number 3841900 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3747149 (Why is no real title available?)
• scientific article; zbMATH DE number 508964 (Why is no real title available?)
• scientific article; zbMATH DE number 861418 (Why is no real title available?)
• scientific article; zbMATH DE number 3270498 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A Characterization of Block-Graphs
• An Elementary Theorem on Graphs
• Binary trees with the largest number of subtrees
• Correlation of Graph‐Theoretical Indices
• Distance in graphs
• Enumeration of subtrees of trees
• Further analysis on the total number of subtrees of trees
• Greedy trees, subtrees and antichains
• Largest Number of Subtrees of Trees with a Given Maximum Degree
• Leaf-induced subtrees of leaf-Fibonacci trees
• Mean distance in a graph
• Minimally 2-connected graphs.
• Monotonicity of the mean order of subtrees
• On subtrees of trees
• On the average number of nodes in a subtree of a tree
• On the sum of all distances in a graph or digraph
• The sum of the distances between the leaves of a tree and the `semi-regular' property

Cited in

(6)

• Maximising the number of connected induced subgraphs of unicyclic graphs
• Upper bounds for some graph invariants in terms of blocks and cut-vertices
• Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs
• On the number of cut-vertices in a graph
• The number of subtrees in graphs with given number of cut edges
• Extremal problems for connected set enumeration

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Cut and pendant vertices and the number of connected induced subgraphs of a graph

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