Large ( d , D , D ′, s )-bipartite digraphs
Identifieur interne : 000232 ( Istex/Corpus ); précédent : 000231; suivant : 000233Large ( d , D , D ′, s )-bipartite digraphs
Auteurs : J. G Mez ; P. Morillo ; C. PadrSource :
- Discrete Applied Mathematics [ 0166-218X ] ; 1992.
Abstract
A (d, D, D′, s)-digraph is a directed graph with diameter D and maximum out-degree d such that after the deletion of any s of its vertices the resulting digraph has diameter at most D′. Our concern is to find large, i.e. with order as large as possible, (d, D, D′, s)-bipartite digraphs. To this end, it is proved that some members of a known family of large bipartite digraphs satisfy a Menger-type condition. Namely, between any pair of non-adjacent vertices they have s + 1 internally disjoint paths of length at most D′. Then, a new family of (d, D, D′, s)-bipartite digraphs with order very close to the upper bound is obtained.
Url:
DOI: 10.1016/0166-218X(93)E0165-U
Links to Exploration step
ISTEX:A0593F7527B5A57BDD97D50285EB0A53A3C63829Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Large ( d , D , D ′, s )-bipartite digraphs</title><author><name sortKey="G Mez, J" sort="G Mez, J" uniqKey="G Mez J" first="J." last="G Mez">J. G Mez</name><affiliation><mods:affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 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àlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</mods:affiliation></affiliation></author><author><name sortKey="Padr, C" sort="Padr, C" uniqKey="Padr C" first="C." last="Padr">C. Padr</name><affiliation><mods:affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:A0593F7527B5A57BDD97D50285EB0A53A3C63829</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1016/0166-218X(93)E0165-U</idno><idno type="url">https://api.istex.fr/document/A0593F7527B5A57BDD97D50285EB0A53A3C63829/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000232</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000232</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Large ( d , D , D ′, s )-bipartite digraphs</title><author><name sortKey="G Mez, J" sort="G Mez, J" uniqKey="G Mez J" first="J." last="G Mez">J. G Mez</name><affiliation><mods:affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 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àlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</mods:affiliation></affiliation></author><author><name sortKey="Padr, C" sort="Padr, C" uniqKey="Padr C" first="C." last="Padr">C. Padr</name><affiliation><mods:affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Discrete Applied Mathematics</title><title level="j" type="abbrev">DAM</title><idno type="ISSN">0166-218X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1992">1992</date><biblScope unit="volume">59</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="103">103</biblScope><biblScope unit="page" to="114">114</biblScope></imprint><idno type="ISSN">0166-218X</idno></series><idno type="istex">A0593F7527B5A57BDD97D50285EB0A53A3C63829</idno><idno type="DOI">10.1016/0166-218X(93)E0165-U</idno><idno type="PII">0166-218X(93)E0165-U</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0166-218X</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">A (d, D, D′, s)-digraph is a directed graph with diameter D and maximum out-degree d such that after the deletion of any s of its vertices the resulting digraph has diameter at most D′. Our concern is to find large, i.e. with order as large as possible, (d, D, D′, s)-bipartite digraphs. To this end, it is proved that some members of a known family of large bipartite digraphs satisfy a Menger-type condition. Namely, between any pair of non-adjacent vertices they have s + 1 internally disjoint paths of length at most D′. Then, a new family of (d, D, D′, s)-bipartite digraphs with order very close to the upper bound is obtained.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>J. Gómez</name><affiliations><json:string>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</json:string></affiliations></json:item><json:item><name>P. Morillo</name><affiliations><json:string>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</json:string></affiliations></json:item><json:item><name>C. Padró</name><affiliations><json:string>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><abstract>A (d, D, D′, s)-digraph is a directed graph with diameter D and maximum out-degree d such that after the deletion of any s of its vertices the resulting digraph has diameter at most D′. Our concern is to find large, i.e. with order as large as possible, (d, D, D′, s)-bipartite digraphs. To this end, it is proved that some members of a known family of large bipartite digraphs satisfy a Menger-type condition. Namely, between any pair of non-adjacent vertices they have s + 1 internally disjoint paths of length at most D′. Then, a new family of (d, D, D′, s)-bipartite digraphs with order very close to the upper bound is obtained.</abstract><qualityIndicators><score>6.089</score><pdfVersion>1.2</pdfVersion><pdfPageSize>468 x 684 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>633</abstractCharCount><pdfWordCount>4721</pdfWordCount><pdfCharCount>19450</pdfCharCount><pdfPageCount>12</pdfPageCount><abstractWordCount>114</abstractWordCount></qualityIndicators><title>Large ( d , D , D ′, s )-bipartite digraphs</title><pii><json:string>0166-218X(93)E0165-U</json:string></pii><genre><json:string>research-article</json:string></genre><serie><genre></genre><language><json:string>unknown</json:string></language><title>Thesis</title></serie><host><volume>59</volume><pii><json:string>S0166-218X(00)X0019-4</json:string></pii><pages><last>114</last><first>103</first></pages><issn><json:string>0166-218X</json:string></issn><issue>2</issue><genre><json:string>Journal</json:string></genre><language><json:string>unknown</json:string></language><title>Discrete Applied Mathematics</title><publicationDate>1995</publicationDate></host><categories><wos><json:string>MATHEMATICS, APPLIED</json:string></wos></categories><publicationDate>1992</publicationDate><copyrightDate>1995</copyrightDate><doi><json:string>10.1016/0166-218X(93)E0165-U</json:string></doi><id>A0593F7527B5A57BDD97D50285EB0A53A3C63829</id><score>1</score><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/A0593F7527B5A57BDD97D50285EB0A53A3C63829/fulltext/pdf</uri></json:item><json:item><original>true</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/A0593F7527B5A57BDD97D50285EB0A53A3C63829/fulltext/txt</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/A0593F7527B5A57BDD97D50285EB0A53A3C63829/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/A0593F7527B5A57BDD97D50285EB0A53A3C63829/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Large ( d , D , D ′, s )-bipartite digraphs</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1995</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Large ( d , D , D ′, s )-bipartite digraphs</title><author><persName><forename type="first">J.</forename><surname>Gómez</surname></persName><affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</affiliation></author><author><persName><forename type="first">P.</forename><surname>Morillo</surname></persName><affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</affiliation></author><author><persName><forename type="first">C.</forename><surname>Padró</surname></persName><note type="correspondence"><p>Corresponding author.</p></note><affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</affiliation></author></analytic><monogr><title level="j">Discrete Applied Mathematics</title><title level="j" type="abbrev">DAM</title><idno type="pISSN">0166-218X</idno><idno type="PII">S0166-218X(00)X0019-4</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1992"></date><biblScope unit="volume">59</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="103">103</biblScope><biblScope unit="page" to="114">114</biblScope></imprint></monogr><idno type="istex">A0593F7527B5A57BDD97D50285EB0A53A3C63829</idno><idno type="DOI">10.1016/0166-218X(93)E0165-U</idno><idno type="PII">0166-218X(93)E0165-U</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1995</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>A (d, D, D′, s)-digraph is a directed graph with diameter D and maximum out-degree d such that after the deletion of any s of its vertices the resulting digraph has diameter at most D′. Our concern is to find large, i.e. with order as large as possible, (d, D, D′, s)-bipartite digraphs. To this end, it is proved that some members of a known family of large bipartite digraphs satisfy a Menger-type condition. Namely, between any pair of non-adjacent vertices they have s + 1 internally disjoint paths of length at most D′. Then, a new family of (d, D, D′, s)-bipartite digraphs with order very close to the upper bound is obtained.</p></abstract></profileDesc><revisionDesc><change when="1992-02-18">Received</change><change when="1993-05-26">Modified</change><change when="1992">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>DAM</jid><aid>93E0165U</aid><ce:pii>0166-218X(93)E0165-U</ce:pii><ce:doi>10.1016/0166-218X(93)E0165-U</ce:doi><ce:copyright type="unknown" year="1995"></ce:copyright></item-info><head><ce:title>Large (<ce:italic>d</ce:italic>, <ce:italic>D</ce:italic>, <ce:italic>D</ce:italic>′, <ce:italic>s</ce:italic>)-bipartite digraphs</ce:title><ce:author-group><ce:author><ce:given-name>J.</ce:given-name><ce:surname>Gómez</ce:surname></ce:author><ce:author><ce:given-name>P.</ce:given-name><ce:surname>Morillo</ce:surname></ce:author><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:affiliation><ce:textfn>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 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="18" month="2" year="1992"></ce:date-received><ce:date-revised day="26" month="5" year="1993"></ce:date-revised><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>A (<ce:italic>d</ce:italic>, <ce:italic>D</ce:italic>, <ce:italic>D</ce:italic>′, <ce:italic>s</ce:italic>)-digraph is a directed graph with diameter <ce:italic>D</ce:italic> and maximum out-degree <ce:italic>d</ce:italic> such that after the deletion of any <ce:italic>s</ce:italic> of its vertices the resulting digraph has diameter at most <ce:italic>D</ce:italic>′. Our concern is to find large, i.e. with order as large as possible, (<ce:italic>d</ce:italic>, <ce:italic>D</ce:italic>, <ce:italic>D</ce:italic>′, <ce:italic>s</ce:italic>)-bipartite digraphs. To this end, it is proved that some members of a known family of large bipartite digraphs satisfy a Menger-type condition. Namely, between any pair of non-adjacent vertices they have <ce:italic>s</ce:italic> + 1 internally disjoint paths of length at most <ce:italic>D</ce:italic>′. Then, a new family of (<ce:italic>d</ce:italic>, <ce:italic>D</ce:italic>, <ce:italic>D</ce:italic>′, <ce:italic>s</ce:italic>)-bipartite digraphs with order very close to the upper bound is obtained.</ce:simple-para></ce:abstract-sec></ce:abstract></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Large ( d , D , D ′, s )-bipartite digraphs</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Large (</title></titleInfo><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Gómez</namePart><affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</affiliation><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àlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Padró</namePart><affiliation>Departament de Matemàlica, Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Apdo. 30.002, 08080 Barcelona, Spain</affiliation><description>Corresponding author.</description><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">1992</dateIssued><dateCaptured encoding="w3cdtf">1992-02-18</dateCaptured><dateModified encoding="w3cdtf">1993-05-26</dateModified><copyrightDate encoding="w3cdtf">1995</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">A (d, D, D′, s)-digraph is a directed graph with diameter D and maximum out-degree d such that after the deletion of any s of its vertices the resulting digraph has diameter at most D′. Our concern is to find large, i.e. with order as large as possible, (d, D, D′, s)-bipartite digraphs. To this end, it is proved that some members of a known family of large bipartite digraphs satisfy a Menger-type condition. Namely, between any pair of non-adjacent vertices they have s + 1 internally disjoint paths of length at most D′. Then, a new family of (d, D, D′, s)-bipartite digraphs with order very close to the upper bound is obtained.</abstract><relatedItem type="host"><titleInfo><title>Discrete Applied Mathematics</title></titleInfo><titleInfo type="abbreviated"><title>DAM</title></titleInfo><genre type="Journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">19950512</dateIssued></originInfo><identifier type="ISSN">0166-218X</identifier><identifier type="PII">S0166-218X(00)X0019-4</identifier><part><date>19950512</date><detail type="volume"><number>59</number><caption>vol.</caption></detail><detail type="issue"><number>2</number><caption>no.</caption></detail><extent unit="issue pages"><start>103</start><end>202</end></extent><extent unit="pages"><start>103</start><end>114</end></extent></part></relatedItem><identifier type="istex">A0593F7527B5A57BDD97D50285EB0A53A3C63829</identifier><identifier type="DOI">10.1016/0166-218X(93)E0165-U</identifier><identifier type="PII">0166-218X(93)E0165-U</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 000232 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000232 | 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:A0593F7527B5A57BDD97D50285EB0A53A3C63829
|texte= Large ( d , D , D ′, s )-bipartite digraphs
}}
| This area was generated with Dilib version V0.6.31. |  |