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. | ![]() |