Proper connection numbers of complementary graphs

DOI10.1007/S40840-016-0381-8MaRDI QIDQ723592zbMATH OpenOpenAlexFDO

Authors F. Huang, Shujing Wang, Xueliang Li

Publication date 24 July 2018

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/1504.02414

zbMATH Keywords

diametercomplement graphNordhaus-Gaddum-typeproper connection numberproper path

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: A path $P$ in an edge-colored graph $G$ is called a proper path if no two adjacent edges of $P$ are colored the same, and $G$ is proper connected if every two vertices of $G$ are connected by a proper path in $G$. The proper connection number of a connected graph $G$, denoted by $pc(G)$, is the minimum number of colors that are needed to make $G$ proper connected. In this paper, we investigate the proper connection number of the complement of graph $G$ according to some constraints of $G$ itself. Also, we characterize the graphs on $n$ vertices that have proper connection number $n-2$. Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if $G$ and $overlineG$ are both connected, then $4lepc(G)+pc(overlineG)len$, and the only graph attaining the upper bound is the tree with maximum degree $Delta=n-2$.

Recommendations

• Nordhaus-Gaddum-type theorem for total-proper connection number of graphs
• Sharp Nordhaus-Gaddum-type lower bounds for proper connection numbers of graphs
• Proper connection and size of graphs
• Upper bounds of proper connection number of graphs
• Proper connection with many colors

Cites work

• Graph theory
• Nordhaus-Gaddum inequalities for domination in graphs
• Nordhaus-Gaddum-type bounds for the rainbow vertex-connection number of a graph
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• On Complementary Graphs
• On proper-path colorings in graphs
• Proper connection of graphs
• Rainbow connection in 3-connected graphs
• Rainbow connection in graphs
• Rainbow connection number and connected dominating sets
• Rainbow connection numbers of complementary graphs
• Rainbow connection of graphs with diameter 2
• The Diameter of a Graph and its Complement
• The rainbow connectivity of a graph

Cited in

(15)

• Some results on (strong) total proper connection number of some digraphs
• Degree sums and proper connection number of graphs
• The connectivity of a graph and its complement
• Upper bounds of proper connection number of graphs
• Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs
• Some results on the total proper \(k\)-connection number
• Proper connection number and connected dominating sets
• Proper connection number of graph products
• Sharp Nordhaus-Gaddum-type lower bounds for proper connection numbers of graphs
• Nordhaus-Gaddum-type theorem for total-proper connection number of graphs
• Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\)
• Proper connection number 2, connectivity, and forbidden subgraphs
• On two conjectures about the proper connection number of graphs
• scientific article; zbMATH DE number 897189 (Why is no real title available?)
• Minimum degree condition for proper connection number 2

This page was built for publication: Proper connection numbers of complementary graphs

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