Proper connection numbers of complementary graphs

DOI10.1007/S40840-016-0381-8zbMATH Open1393.05179arXiv1504.02414OpenAlexW1629130479MaRDI QIDQ723592FDOQ723592

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)

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

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

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

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)

Cites Work

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

Cited In (15)

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

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)