Diameter vulnerability of iterated line digraphs
Identifieur interne : 003B63 ( Istex/Corpus ); précédent : 003B62; suivant : 003B64Diameter vulnerability of iterated line digraphs
Auteurs : C. Padr ; P. MorilloSource :
- Discrete Mathematics [ 0012-365X ] ; 1993.
Abstract
Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For any digraph G, we find a constant C (not greater than twice the diameter of G) such that, under certain conditions, the diameter vulnerability of the iterated line digraph Lk G is at most the diameter of Lk G plus C. The results in this paper generalize previous results on the diameter-vulnerability of particular families of iterated line digraphs (Kautz and de Bruijn digraphs).
Url:
DOI: 10.1016/0012-365X(96)83094-9
Links to Exploration step
ISTEX:58556E30991C3099220FC20A739F585A90AD8CC6Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Diameter vulnerability of iterated line digraphs</title>
<author><name sortKey="Padr, C" sort="Padr, C" uniqKey="Padr C" first="C." last="Padr">C. Padr</name>
<affiliation><mods:affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Morillo, P" sort="Morillo, P" uniqKey="Morillo P" first="P." last="Morillo">P. Morillo</name>
<affiliation><mods:affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</mods:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:58556E30991C3099220FC20A739F585A90AD8CC6</idno>
<date when="1996" year="1996">1996</date>
<idno type="doi">10.1016/0012-365X(96)83094-9</idno>
<idno type="url">https://api.istex.fr/document/58556E30991C3099220FC20A739F585A90AD8CC6/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">003B63</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003B63</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a">Diameter vulnerability of iterated line digraphs</title>
<author><name sortKey="Padr, C" sort="Padr, C" uniqKey="Padr C" first="C." last="Padr">C. Padr</name>
<affiliation><mods:affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Morillo, P" sort="Morillo, P" uniqKey="Morillo P" first="P." last="Morillo">P. Morillo</name>
<affiliation><mods:affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</mods:affiliation>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Discrete Mathematics</title>
<title level="j" type="abbrev">DISC</title>
<idno type="ISSN">0012-365X</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1993">1993</date>
<biblScope unit="volume">149</biblScope>
<biblScope unit="issue">1–3</biblScope>
<biblScope unit="page" from="189">189</biblScope>
<biblScope unit="page" to="204">204</biblScope>
</imprint>
<idno type="ISSN">0012-365X</idno>
</series>
<idno type="istex">58556E30991C3099220FC20A739F585A90AD8CC6</idno>
<idno type="DOI">10.1016/0012-365X(96)83094-9</idno>
<idno type="PII">0012-365X(96)83094-9</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0012-365X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For any digraph G, we find a constant C (not greater than twice the diameter of G) such that, under certain conditions, the diameter vulnerability of the iterated line digraph Lk G is at most the diameter of Lk G plus C. The results in this paper generalize previous results on the diameter-vulnerability of particular families of iterated line digraphs (Kautz and de Bruijn digraphs).</div>
</front>
</TEI>
<istex><corpusName>elsevier</corpusName>
<author><json:item><name>C. Padró</name>
<affiliations><json:string>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</json:string>
</affiliations>
</json:item>
<json:item><name>P. Morillo</name>
<affiliations><json:string>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</json:string>
</affiliations>
</json:item>
</author>
<language><json:string>eng</json:string>
</language>
<abstract>Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For any digraph G, we find a constant C (not greater than twice the diameter of G) such that, under certain conditions, the diameter vulnerability of the iterated line digraph Lk G is at most the diameter of Lk G plus C. The results in this paper generalize previous results on the diameter-vulnerability of particular families of iterated line digraphs (Kautz and de Bruijn digraphs).</abstract>
<qualityIndicators><score>6.296</score>
<pdfVersion>1.2</pdfVersion>
<pdfPageSize>540 x 742 pts</pdfPageSize>
<refBibsNative>true</refBibsNative>
<keywordCount>0</keywordCount>
<abstractCharCount>680</abstractCharCount>
<pdfWordCount>9002</pdfWordCount>
<pdfCharCount>32900</pdfCharCount>
<pdfPageCount>16</pdfPageCount>
<abstractWordCount>108</abstractWordCount>
</qualityIndicators>
<title>Diameter vulnerability of iterated line digraphs</title>
<pii><json:string>0012-365X(96)83094-9</json:string>
</pii>
<genre><json:string>research-article</json:string>
</genre>
<serie><pages><last>30</last>
<first>1</first>
</pages>
<genre></genre>
<language><json:string>unknown</json:string>
</language>
<title>Surveys in Combinatorics</title>
</serie>
<host><volume>149</volume>
<pii><json:string>S0012-365X(00)X0006-4</json:string>
</pii>
<pages><last>204</last>
<first>189</first>
</pages>
<issn><json:string>0012-365X</json:string>
</issn>
<issue>1–3</issue>
<genre><json:string>Journal</json:string>
</genre>
<language><json:string>unknown</json:string>
</language>
<title>Discrete Mathematics</title>
<publicationDate>1996</publicationDate>
</host>
<categories><wos><json:string>MATHEMATICS</json:string>
</wos>
</categories>
<publicationDate>1993</publicationDate>
<copyrightDate>1996</copyrightDate>
<doi><json:string>10.1016/0012-365X(96)83094-9</json:string>
</doi>
<id>58556E30991C3099220FC20A739F585A90AD8CC6</id>
<score>1</score>
<fulltext><json:item><original>true</original>
<mimetype>application/pdf</mimetype>
<extension>pdf</extension>
<uri>https://api.istex.fr/document/58556E30991C3099220FC20A739F585A90AD8CC6/fulltext/pdf</uri>
</json:item>
<json:item><original>true</original>
<mimetype>text/plain</mimetype>
<extension>txt</extension>
<uri>https://api.istex.fr/document/58556E30991C3099220FC20A739F585A90AD8CC6/fulltext/txt</uri>
</json:item>
<json:item><original>false</original>
<mimetype>application/zip</mimetype>
<extension>zip</extension>
<uri>https://api.istex.fr/document/58556E30991C3099220FC20A739F585A90AD8CC6/fulltext/zip</uri>
</json:item>
<istex:fulltextTEI uri="https://api.istex.fr/document/58556E30991C3099220FC20A739F585A90AD8CC6/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Diameter vulnerability of iterated line digraphs</title>
</titleStmt>
<publicationStmt><authority>ISTEX</authority>
<publisher>ELSEVIER</publisher>
<availability><p>ELSEVIER</p>
</availability>
<date>1996</date>
</publicationStmt>
<sourceDesc><biblStruct type="inbook"><analytic><title level="a">Diameter vulnerability of iterated line digraphs</title>
<author><persName><forename type="first">C.</forename>
<surname>Padró</surname>
</persName>
<note type="correspondence"><p>Corresponding author.</p>
</note>
<affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</affiliation>
</author>
<author><persName><forename type="first">P.</forename>
<surname>Morillo</surname>
</persName>
<affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</affiliation>
</author>
</analytic>
<monogr><title level="j">Discrete Mathematics</title>
<title level="j" type="abbrev">DISC</title>
<idno type="pISSN">0012-365X</idno>
<idno type="PII">S0012-365X(00)X0006-4</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1993"></date>
<biblScope unit="volume">149</biblScope>
<biblScope unit="issue">1–3</biblScope>
<biblScope unit="page" from="189">189</biblScope>
<biblScope unit="page" to="204">204</biblScope>
</imprint>
</monogr>
<idno type="istex">58556E30991C3099220FC20A739F585A90AD8CC6</idno>
<idno type="DOI">10.1016/0012-365X(96)83094-9</idno>
<idno type="PII">0012-365X(96)83094-9</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><creation><date>1996</date>
</creation>
<langUsage><language ident="en">en</language>
</langUsage>
<abstract xml:lang="en"><p>Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For any digraph G, we find a constant C (not greater than twice the diameter of G) such that, under certain conditions, the diameter vulnerability of the iterated line digraph Lk G is at most the diameter of Lk G plus C. The results in this paper generalize previous results on the diameter-vulnerability of particular families of iterated line digraphs (Kautz and de Bruijn digraphs).</p>
</abstract>
</profileDesc>
<revisionDesc><change when="1993-07-07">Received</change>
<change when="1994-06-03">Modified</change>
<change when="1993">Published</change>
</revisionDesc>
</teiHeader>
</istex:fulltextTEI>
</fulltext>
<metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration>
<istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType>
<istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>DISC</jid>
<aid>96830949</aid>
<ce:pii>0012-365X(96)83094-9</ce:pii>
<ce:doi>10.1016/0012-365X(96)83094-9</ce:doi>
<ce:copyright type="unknown" year="1996"></ce:copyright>
</item-info>
<head><ce:title>Diameter vulnerability of iterated line digraphs</ce:title>
<ce:author-group><ce:author><ce:given-name>C.</ce:given-name>
<ce:surname>Padró</ce:surname>
<ce:cross-ref refid="COR1"><ce:sup>∗</ce:sup>
</ce:cross-ref>
</ce:author>
<ce:author><ce:given-name>P.</ce:given-name>
<ce:surname>Morillo</ce:surname>
</ce:author>
<ce:affiliation><ce:textfn>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</ce:textfn>
</ce:affiliation>
<ce:correspondence id="COR1"><ce:label>∗</ce:label>
<ce:text>Corresponding author.</ce:text>
</ce:correspondence>
</ce:author-group>
<ce:date-received day="7" month="7" year="1993"></ce:date-received>
<ce:date-revised day="3" month="6" year="1994"></ce:date-revised>
<ce:abstract><ce:section-title>Abstract</ce:section-title>
<ce:abstract-sec><ce:simple-para>Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For any digraph <ce:italic>G</ce:italic>
, we find a constant <ce:italic>C</ce:italic>
(not greater than twice the diameter of <ce:italic>G</ce:italic>
) such that, under certain conditions, the diameter vulnerability of the iterated line digraph <ce:italic>L</ce:italic>
<ce:sup><ce:italic>k</ce:italic>
</ce:sup>
<ce:italic>G</ce:italic>
is at most the diameter of <ce:italic>L</ce:italic>
<ce:sup><ce:italic>k</ce:italic>
</ce:sup>
<ce:italic>G</ce:italic>
plus <ce:italic>C</ce:italic>
. The results in this paper generalize previous results on the diameter-vulnerability of particular families of iterated line digraphs (Kautz and de Bruijn digraphs).</ce:simple-para>
</ce:abstract-sec>
</ce:abstract>
</head>
</converted-article>
</istex:document>
</istex:metadataXml>
<mods version="3.6"><titleInfo><title>Diameter vulnerability of iterated line digraphs</title>
</titleInfo>
<titleInfo type="alternative" contentType="CDATA"><title>Diameter vulnerability of iterated line digraphs</title>
</titleInfo>
<name type="personal"><namePart type="given">C.</namePart>
<namePart type="family">Padró</namePart>
<affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</affiliation>
<description>Corresponding author.</description>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<name type="personal"><namePart type="given">P.</namePart>
<namePart type="family">Morillo</namePart>
<affiliation>Departament de Matemàtica Aplicada i Telematica, Universitat Politècnica de Catalunya, C/Gran Capità s/n, 08034 Barcelona, Spain</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<typeOfResource>text</typeOfResource>
<genre type="research-article" displayLabel="Full-length article"></genre>
<originInfo><publisher>ELSEVIER</publisher>
<dateIssued encoding="w3cdtf">1993</dateIssued>
<dateCaptured encoding="w3cdtf">1993-07-07</dateCaptured>
<dateModified encoding="w3cdtf">1994-06-03</dateModified>
<copyrightDate encoding="w3cdtf">1996</copyrightDate>
</originInfo>
<language><languageTerm type="code" authority="iso639-2b">eng</languageTerm>
<languageTerm type="code" authority="rfc3066">en</languageTerm>
</language>
<physicalDescription><internetMediaType>text/html</internetMediaType>
</physicalDescription>
<abstract lang="en">Because of their good properties, iterated line digraphs (specially Kautz and de Bruijn digraphs) have been considered to design interconnection networks. The diameter-vulnerability of a digraph is the maximum diameter of the subdigraphs obtained by deleting a fixed number of vertices or arcs. For any digraph G, we find a constant C (not greater than twice the diameter of G) such that, under certain conditions, the diameter vulnerability of the iterated line digraph Lk G is at most the diameter of Lk G plus C. The results in this paper generalize previous results on the diameter-vulnerability of particular families of iterated line digraphs (Kautz and de Bruijn digraphs).</abstract>
<relatedItem type="host"><titleInfo><title>Discrete Mathematics</title>
</titleInfo>
<titleInfo type="abbreviated"><title>DISC</title>
</titleInfo>
<genre type="Journal">journal</genre>
<originInfo><dateIssued encoding="w3cdtf">19960222</dateIssued>
</originInfo>
<identifier type="ISSN">0012-365X</identifier>
<identifier type="PII">S0012-365X(00)X0006-4</identifier>
<part><date>19960222</date>
<detail type="volume"><number>149</number>
<caption>vol.</caption>
</detail>
<detail type="issue"><number>1–3</number>
<caption>no.</caption>
</detail>
<extent unit="issue pages"><start>1</start>
<end>330</end>
</extent>
<extent unit="pages"><start>189</start>
<end>204</end>
</extent>
</part>
</relatedItem>
<identifier type="istex">58556E30991C3099220FC20A739F585A90AD8CC6</identifier>
<identifier type="DOI">10.1016/0012-365X(96)83094-9</identifier>
<identifier type="PII">0012-365X(96)83094-9</identifier>
<recordInfo><recordContentSource>ELSEVIER</recordContentSource>
</recordInfo>
</mods>
</metadata>
</istex>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003B63 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 003B63 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Ticri/CIDE |area= TelematiV1 |flux= Istex |étape= Corpus |type= RBID |clé= ISTEX:58556E30991C3099220FC20A739F585A90AD8CC6 |texte= Diameter vulnerability of iterated line digraphs }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |