Connectivity of the Mycielskian of a graph

DOI10.1016/J.DISC.2007.05.004MaRDI QIDQ2427520zbMATH OpenOpenAlexFDO

Authors R. Balakrishnan, S. Francis Raj

Publication date 13 May 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.05.004

zbMATH Keywords

edge-connectivityMycielskianvertex-connectivity

Mathematics Subject Classification ID

Connectivity (05C40)

Review text

For triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph \(G\) into a new graph \(\mu(G)\). This short paper study the vertex-connectivity \(k(\mu(G))\) and edge-connectivity \(k'(\mu(G))\) of \(\mu(G)\). The authors prove that \(k(\mu(G))= \min\{\delta(\mu(G)),2k(G)+1\}\) and \(k'(\mu(G))= \delta(\mu(G))\), where \(\delta(G)\) is the minimum degree of \(G\).

Recommendations

• Connectivity of the Mycielskian of a digraph
• The generalized 3-connectivity of the Mycielskian of a graph
• Connectivity of the generalised Mycielskian of digraphs
• Super connectivity and super arc connectivity of the Mycielskian of a digraph.
• D-Mycielskian graph of a graph

Cites work

• A textbook of graph theory
• Circular chromatic number and a generalization of the construction of Mycielski.
• Circular chromatic number and Mycielski construction
• Circular chromatic number and Mycielski graphs
• Circular chromatic number for iterated Mycielski graphs
• Circular chromatic numbers of Mycielski's graphs
• Connectivity of transitive graphs
• Eine Eigenschaft der Atome endlicher Graphen
• Sur le coloriage des graphs

Cited in

(23)

• Packing chromatic number versus chromatic and clique number
• Super connectivity and super edge connectivity of the Mycielskian of a graph
• The generalized 3-connectivity of the Mycielskian of a graph
• The hub number, girth and Mycielski graphs
• Hamilton-connected Mycielski \(\mathrm{graphs}^\ast\)
• Simple graphs as simplicial complexes: the Mycielskian of a graph
• On the total graph of Mycielski graphs, central graphs and their covering numbers
• A note on Mycielskian type of a graph
• Super connectivity and super arc connectivity of the Mycielskian of a digraph.
• Some network topological notions of the Mycielskian of a graph
• Connectivity of the generalised Mycielskian of digraphs
• D-Mycielskian graph of a graph
• Color stable graphs
• Wiener index of the tensor product of cycles
• Several parameters of the complement of generalized Mycielskian graph
• Indicated coloring of the Mycielskian of some families of graphs
• On the general position number of Mycielskian graphs
• Power domination in Mycielskians of n -spiders
• Power domination in generalized Mycielskian of cycles
• Indicated coloring of some families of graphs
• Determining number and cost of generalized Mycielskian graphs
• Power domination in generalized Mycielskian of spiders
• Connectivity of the Mycielskian of a digraph

This page was built for publication: Connectivity of the Mycielskian of a graph

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