Cycle-connected graphs

DOI10.1016/0012-365X(92)90680-EMaRDI QIDQ1201258zbMATH OpenOpenAlexWikidataFDO

Authors Richard A. Duke, Vojtěch Rödl, P. Erdős

Publication date 17 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90680-e

zbMATH Keywords

cycle-connected graphsmultipartite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40)

Review text

A graph \(G\) is called \(K\)-connected, \(K\) a fixed collection of graphs, if every pair of edges of \(G\) is contained in a subgraph \(S\) of \(G\), where \(S\in K\). The authors discuss \(C_4\)-connected graphs, where \(C_4\) is a cycle of length four and compute the constant \(c\) such that there exists a graph with \(cn^2\) edges \((n = |V(G)|)\) in which the largest \(C_4\)-connected subgraph has size at most \(c\).

Recommendations

• scientific article; zbMATH DE number 140120
• scientific article; zbMATH DE number 2191994
• The cycle in 2-connected \([4,2]\)-graphs
• On the edge-connectivity of C₄-free graphs
• Cyclability in \(k\)-connected \(K_{1,4}\)-free graphs

Cites work

• scientific article; zbMATH DE number 3884200 (Why is no real title available?)
• scientific article; zbMATH DE number 3891408 (Why is no real title available?)
• scientific article; zbMATH DE number 3813668 (Why is no real title available?)
• scientific article; zbMATH DE number 4103103 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The Erdős-Ko-Rado theorem for small families

Cited in

(17)

• Cycles in graphs with prescribed stability number and connectivity
• Cyclic Haar graphs
• Tutte cycles in circuit graphs
• Distinguishing graphs via cycles
• Cycle connectivity in weighted graphs
• scientific article; zbMATH DE number 6096657 (Why is no real title available?)
• scientific article; zbMATH DE number 3873365 (Why is no real title available?)
• scientific article; zbMATH DE number 1382546 (Why is no real title available?)
• scientific article; zbMATH DE number 140120 (Why is no real title available?)
• On large intersecting subfamilies of uniform setfamilies
• The edge \(C_k\) graph of a graph
• On the edge-connectivity of C₄-free graphs
• The cycle in 2-connected \([4,2]\)-graphs
• scientific article; zbMATH DE number 4183444 (Why is no real title available?)
• Additional Closeness of Cycle Graphs
• Cyclability in \(k\)-connected \(K_{1,4}\)-free graphs
• On a problem of Duke-Erdős-Rödl on cycle-connected subgraphs

This page was built for publication: Cycle-connected graphs

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