Robust cycle bases do not exist for K^sub n,n^ if n = 8

A basis for the cycle space of a graph is said to be robust if any cycle Z of G is a sum Z=C1+C2+⋯+Ck of basis elements such that (i) (C1+C2+⋯+Cl-1)∩Cl is a nontrivial path for each 2≤l

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-01, Vol.235, p.206
Main Authors: Hammack, Richard H, Kainen, Paul C
Format: Article
Language:English
Subjects:
Graphs
Robustness
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page 206
container_title Discrete Applied Mathematics
container_volume 235
creator Hammack, Richard H
Kainen, Paul C
description A basis for the cycle space of a graph is said to be robust if any cycle Z of G is a sum Z=C1+C2+⋯+Ck of basis elements such that (i) (C1+C2+⋯+Cl-1)∩Cl is a nontrivial path for each 2≤l
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_1990827442</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1990827442</sourcerecordid><originalsourceid>FETCH-proquest_journals_19908274423</originalsourceid><addsrcrecordid>eNpjYuA0tDA30jUzNzdkYeA0MDQz0zUytIjgYOAqLs4yAAJDCzNOBvOg_KTS4hKF5MrknFSFpMTi1GKFlHyFvPwShdSKTKBEWn6RgndccWmSQp5OXpxCZppCnoKtggUPA2taYk5xKi-U5mZQdnMNcfbQLSjKLyxNLS6Jz8ovLcoDSsUbWloaWBiZm5gYGROnCgBGPTU-</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1990827442</pqid></control><display><type>article</type><title>Robust cycle bases do not exist for K^sub n,n^ if n = 8</title><source>Elsevier</source><creator>Hammack, Richard H ; Kainen, Paul C</creator><creatorcontrib>Hammack, Richard H ; Kainen, Paul C</creatorcontrib><description>A basis for the cycle space of a graph is said to be robust if any cycle Z of G is a sum Z=C1+C2+⋯+Ck of basis elements such that (i) (C1+C2+⋯+Cl-1)∩Cl is a nontrivial path for each 2≤l&lt;k. Hence, (ii) each partial sum C1+C2+⋯+Cl is a cycle for 1≤l≤k. While complete graphs and 2-connected plane graphs have robust cycle bases, it is shown that regular complete bipartite graphs Kn,n do not have any robust cycle basis if n≥8.</description><identifier>ISSN: 0166-218X</identifier><identifier>EISSN: 1872-6771</identifier><language>eng</language><publisher>Amsterdam: Elsevier BV</publisher><subject>Graphs ; Robustness ; Studies</subject><ispartof>Discrete Applied Mathematics, 2018-01, Vol.235, p.206</ispartof><rights>Copyright Elsevier BV Jan 30, 2018</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,777,781</link.rule.ids></links><search><creatorcontrib>Hammack, Richard H</creatorcontrib><creatorcontrib>Kainen, Paul C</creatorcontrib><title>Robust cycle bases do not exist for K^sub n,n^ if n = 8</title><title>Discrete Applied Mathematics</title><description>A basis for the cycle space of a graph is said to be robust if any cycle Z of G is a sum Z=C1+C2+⋯+Ck of basis elements such that (i) (C1+C2+⋯+Cl-1)∩Cl is a nontrivial path for each 2≤l&lt;k. Hence, (ii) each partial sum C1+C2+⋯+Cl is a cycle for 1≤l≤k. While complete graphs and 2-connected plane graphs have robust cycle bases, it is shown that regular complete bipartite graphs Kn,n do not have any robust cycle basis if n≥8.</description><subject>Graphs</subject><subject>Robustness</subject><subject>Studies</subject><issn>0166-218X</issn><issn>1872-6771</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNpjYuA0tDA30jUzNzdkYeA0MDQz0zUytIjgYOAqLs4yAAJDCzNOBvOg_KTS4hKF5MrknFSFpMTi1GKFlHyFvPwShdSKTKBEWn6RgndccWmSQp5OXpxCZppCnoKtggUPA2taYk5xKi-U5mZQdnMNcfbQLSjKLyxNLS6Jz8ovLcoDSsUbWloaWBiZm5gYGROnCgBGPTU-</recordid><startdate>20180130</startdate><enddate>20180130</enddate><creator>Hammack, Richard H</creator><creator>Kainen, Paul C</creator><general>Elsevier BV</general><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20180130</creationdate><title>Robust cycle bases do not exist for K^sub n,n^ if n = 8</title><author>Hammack, Richard H ; Kainen, Paul C</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-proquest_journals_19908274423</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Graphs</topic><topic>Robustness</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hammack, Richard H</creatorcontrib><creatorcontrib>Kainen, Paul C</creatorcontrib><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Discrete Applied Mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hammack, Richard H</au><au>Kainen, Paul C</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Robust cycle bases do not exist for K^sub n,n^ if n = 8</atitle><jtitle>Discrete Applied Mathematics</jtitle><date>2018-01-30</date><risdate>2018</risdate><volume>235</volume><spage>206</spage><pages>206-</pages><issn>0166-218X</issn><eissn>1872-6771</eissn><abstract>A basis for the cycle space of a graph is said to be robust if any cycle Z of G is a sum Z=C1+C2+⋯+Ck of basis elements such that (i) (C1+C2+⋯+Cl-1)∩Cl is a nontrivial path for each 2≤l&lt;k. Hence, (ii) each partial sum C1+C2+⋯+Cl is a cycle for 1≤l≤k. While complete graphs and 2-connected plane graphs have robust cycle bases, it is shown that regular complete bipartite graphs Kn,n do not have any robust cycle basis if n≥8.</abstract><cop>Amsterdam</cop><pub>Elsevier BV</pub></addata></record>
fulltext fulltext
identifier ISSN: 0166-218X
ispartof Discrete Applied Mathematics, 2018-01, Vol.235, p.206
issn 0166-218X
1872-6771
language eng
recordid cdi_proquest_journals_1990827442
source Elsevier
subjects Graphs
Robustness
Studies
title Robust cycle bases do not exist for K^sub n,n^ if n = 8
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-19T16%3A13%3A45IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Robust%20cycle%20bases%20do%20not%20exist%20for%20K%5Esub%20n,n%5E%20if%20n%20=%208&rft.jtitle=Discrete%20Applied%20Mathematics&rft.au=Hammack,%20Richard%20H&rft.date=2018-01-30&rft.volume=235&rft.spage=206&rft.pages=206-&rft.issn=0166-218X&rft.eissn=1872-6771&rft_id=info:doi/&rft_dat=%3Cproquest%3E1990827442%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-proquest_journals_19908274423%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1990827442&rft_id=info:pmid/&rfr_iscdi=true