Maximum cardinality neighbourly sets in quadrilateral free graphs

DOI10.1007/S10878-015-9972-9zbMATH Open1388.90117arXiv1412.8338OpenAlexW3106104785MaRDI QIDQ511689FDOQ511689

K. S. Neethi, Sanjeev Saxena

Publication date: 22 February 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: Neighbourly set of a graph is a subset of edges which either share an end point or are joined by an edge of that graph. The maximum cardinality neighbourly set problem is known to be NP-complete for general graphs. Mahdian (M.Mahdian, On the computational complexity of strong edge coloring, Discrete Applied Mathematics, 118:239-248, 2002) proved that it is in polynomial time for quadrilateral-free graphs and proposed an O(n^{11}) algorithm for the same (along with a note that by a straightforward but lengthy argument it can be proved to be solvable in O(n^5) running time). In this paper we propose an O(n^2) time algorithm for finding a maximum cardinality neighbourly set in a quadrilateral-free graph.

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

zbMATH Keywords

algorithmantimatchinggraphs without \(C_4\)neighbourly setsquadrilateral free graphsstrong edge colouring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Finding and counting given length cycles
• Über ein Problem von K. Zarankiewicz
• On Graphs that do not Contain a Thomsen Graph
• Induced matchings
• Arboricity and Subgraph Listing Algorithms
• Finding a Minimum Circuit in a Graph
• Large Subgraphs without Short Cycles
• Graphs without quadrilaterals
• Total colorings of degenerate graphs
• On the number of edges of quadrilateral-free graphs
• An extremal characterization of the incidence graphs of projective planes
• On the computational complexity of strong edge coloring
• The maximum spectral radius of \(C_4\)-free graphs of given order and size
• Graphs without four-cycles
• Extremal graphs without 4-cycles

   Recommendations

• On the number of edges of quadrilateral-free graphs 👍 👎
• The maximal neighbourhood number of a graph 👍 👎
• On multiplicity of quadrilaterals in complete graphs 👍 👎
• The maximum number of triangles in a \(K_4\)-free graph 👍 👎
• Title not available (Why is that?) 👍 👎
• Independent sets of cardinality \(s\) of maximal outerplanar graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• M-degrees of quadrangle-free planar graphs 👍 👎
• Some bounds on the size of maximum G-free sets in graphs 👍 👎

This page was built for publication: Maximum cardinality neighbourly sets in quadrilateral free graphs

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