För ett positivt heltal s, en s-klubb i en graf G är en uppsättning hörn som inducerar en subgraph av G diameter på de flesta s. Vi studerar en relation av klubbar och kliquer. För ett positivt heltal s, säger vi att en graf klass G har sclique-power egenskap om för varje graf G G, varje maximal klick i G s är en s-club i G. Våra huvudsakliga kombinatoriska resultat visar att både 4-chordala grafer och AT-fria grafer har s-clique-power egenskap för alla s ≥ 2. Detta har olika algoritmiska konsekvenser. I synnerhet visar vi att en maximal s-club i G kan beräknas i polynom tid när G är en ackordal bipartite eller en stark ackord eller ett avstånd ärftlig graf. På svagt ackord diagram, vi får en polynom-tid algoritm när s är ett udda heltal, vilket är bäst möjligt eftersom problemet är NP-hård för jämna värden av s. Vi kompletterar dessa resultat genom att bevisa NP-hårdhet av problemet för varje fast s på 4-chordal grafer. Slutligen, om G är en AT-fri graf, visar vi att problemet kan lösas i polynom tid när s ≥ 2, vilket ger en intressant kontrast till det faktum att problemet är NP-hård för s = 1 på denna graf klass.
För alla s ≥ 1, s-Club kan lösas i polynom tid på ackord bipartite, starkt ackord, och avstånd-ärftliga grafer REF.
Finding clubs in graph classes
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}