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

DOI10.1007/S40879-020-00443-8zbMATH Open1468.05117arXiv1910.04552OpenAlexW3121094638MaRDI QIDQ2040982FDOQ2040982

Authors: Audace A. V. Dossou-Olory 

Publication date: 15 July 2021

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

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].

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

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

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)

Cites Work

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

Cited In (6)

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

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)