Maximum cardinality neighbourly sets in quadrilateral free graphs

DOI10.1007/S10878-015-9972-9MaRDI QIDQ511689zbMATH OpenOpenAlexFDO

Authors K. S. Neethi, Sanjeev Saxena

Publication date 22 February 2017

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

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)

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.

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
• scientific article; zbMATH DE number 6902661
• Independent sets of cardinality \(s\) of maximal outerplanar graphs
• The largest number of maximal independent sets in quasi-unicyclic graphs
• M-degrees of quadrangle-free planar graphs
• Some bounds on the size of maximum G-free sets in graphs

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 687701 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3031694 (Why is no real title available?)
• An extremal characterization of the incidence graphs of projective planes
• Arboricity and Subgraph Listing Algorithms
• Extremal graphs without 4-cycles
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Graphs without four-cycles
• Graphs without quadrilaterals
• Induced matchings
• Large subgraphs without short cycles
• On Graphs that do not Contain a Thomsen Graph
• On the computational complexity of strong edge coloring
• On the number of edges of quadrilateral-free graphs
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• The history of degenerate (bipartite) extremal graph problems
• The maximum spectral radius of \(C_4\)-free graphs of given order and size
• Total colorings of degenerate graphs
• Über ein Problem von K. Zarankiewicz

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)