Proper disconnection of graphs

DOI10.1007/S40840-020-01069-5MaRDI QIDQ2045273zbMATH OpenOpenAlexFDO

Authors You Chen, Meng Ji, Xu Qing Bai, Xueliang Li, Yin Di Weng, Wen-Yan Wu

Publication date 12 August 2021

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

edge-coloringouterplanar graphproper disconnection numberproper edge-cut

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Abstract: For an edge-colored graph $G$, a set $F$ of edges of $G$ is called a emph{proper cut} if $F$ is an edge-cut of $G$ and any pair of adjacent edges in $F$ are assigned by different colors. An edge-colored graph is emph{proper disconnected} if for each pair of distinct vertices of $G$ there exists a proper edge-cut separating them. For a connected graph $G$, the emph{proper disconnection number} of $G$, denoted by $pd(G)$, is the minimum number of colors that are needed in order to make $G$ proper disconnected. In this paper, we first give the exact values of the proper disconnection numbers for some special families of graphs. Next, we obtain a sharp upper bound of $pd(G)$ for a connected graph $G$ of order $n$, i.e, $pd(G)leqminch{i}^{\prime }(G)-1,leftlceilfracn2ightceil$. Finally, we show that for given integers $k$ and $n$, the minimum size of a connected graph $G$ of order $n$ with $pd(G)=k$ is $n-1$ for $k=1$ and $n+2k-4$ for $2leqkleqlceilfracn2ceil$.

Recommendations

• Proper connection and size of graphs
• Proper connection with many colors
• Proper connection of graphs
• Proper connection number 2, connectivity, and forbidden subgraphs
• Rainbow disconnection in graphs

Cites work

• Complexity results for the proper disconnection of graphs
• Graph theory
• Monochromatic disconnection of graphs
• Rainbow disconnection in graphs
• The rainbow vertex-disconnection in graphs

Cited in

(6)

• Complexity results for two kinds of colored disconnections of graphs
• Monochromatic disconnection: Erdős-Gallai-type problems and product graphs
• Upper bounds for the \(M D\)-numbers and characterization of extremal graphs
• The proper vertex-disconnection of graphs
• Completely Disconnecting the Complete Graph
• News on disconnected diagrams

This page was built for publication: Proper disconnection of graphs

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