A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications
“Linearly many faults” is a phenomenon observed by Cheng and Lipták in which a specific structure emerges when a graph is disconnected and often occurs in various interconnection networks. This phenomenon means that if a certain number of vertices or edges are deleted from a graph, the remaining par...
| Principais autores: | , , |
|---|---|
| Formato: | Artigo |
| Idioma: | English |
| Publicado em: |
MDPI AG
2024-01-01
|
| coleção: | Mathematics |
| Assuntos: | |
| Acesso em linha: | https://www.mdpi.com/2227-7390/12/2/268 |
| _version_ | 1827371547684241408 |
|---|---|
| author | Mei-Mei Gu Hong-Xia Yan Jou-Ming Chang |
| author_facet | Mei-Mei Gu Hong-Xia Yan Jou-Ming Chang |
| author_sort | Mei-Mei Gu |
| collection | DOAJ |
| description | “Linearly many faults” is a phenomenon observed by Cheng and Lipták in which a specific structure emerges when a graph is disconnected and often occurs in various interconnection networks. This phenomenon means that if a certain number of vertices or edges are deleted from a graph, the remaining part either stays connected or breaks into one large component along with smaller components with just a few vertices. This phenomenon can be observed in many types of graphs and has important implications for network analysis and optimization. In this paper, we first validate the phenomenon of linearly many faults for surviving graph of a burnt pancake graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> when removing any edge subset with a size of approximately six times <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>λ</mi><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula>. For graph <i>G</i>, the <i>ℓ</i>-component edge connectivity denoted as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mi>ℓ</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> (resp., the <i>ℓ</i>-extra edge connectivity denoted as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>λ</mi><mrow><mo>(</mo><mi>ℓ</mi><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>) is the cardinality of a minimum edge subset <i>S</i> such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>S</mi></mrow></semantics></math></inline-formula> is disconnected and has at least <i>ℓ</i> components (resp., each component of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>S</mi></mrow></semantics></math></inline-formula> has at least <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ℓ</mi><mo>+</mo><mn>1</mn></mrow></semantics></math></inline-formula> vertices). Both <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mi>ℓ</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> and e<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>λ</mi><mrow><mo>(</mo><mi>ℓ</mi><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> are essential metrics for network reliability assessment. Specifically, from the property of “linearly many faults”, we may further prove that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mn>5</mn></msub><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>=</mo><msup><mi>λ</mi><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>+</mo><mn>3</mn><mo>=</mo><mn>4</mn><mi>n</mi><mo>−</mo><mn>3</mn></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>⩾</mo><mn>5</mn></mrow></semantics></math></inline-formula>; <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mn>6</mn></msub><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>=</mo><msup><mi>λ</mi><mrow><mo>(</mo><mn>4</mn><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>+</mo><mn>4</mn><mo>=</mo><mn>5</mn><mi>n</mi><mo>−</mo><mn>4</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mn>7</mn></msub><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>=</mo><msup><mi>λ</mi><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>+</mo><mn>5</mn><mo>=</mo><mn>6</mn><mi>n</mi><mo>−</mo><mn>5</mn></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>⩾</mo><mn>6</mn></mrow></semantics></math></inline-formula>. |
| first_indexed | 2024-03-08T10:42:01Z |
| format | Article |
| id | doaj.art-1acf55d22a9b46f4bcd6fe028e67406e |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-08T10:42:01Z |
| publishDate | 2024-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-1acf55d22a9b46f4bcd6fe028e67406e2024-01-26T17:32:36ZengMDPI AGMathematics2227-73902024-01-0112226810.3390/math12020268A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its ApplicationsMei-Mei Gu0Hong-Xia Yan1Jou-Ming Chang2Department of Science and Technology, China University of Political Science and Law, Beijing 102249, ChinaDepartment of Science and Technology, China University of Political Science and Law, Beijing 102249, ChinaInstitute of Information and Decision Sciences, National Taipei University of Business, Taipei 10051, Taiwan“Linearly many faults” is a phenomenon observed by Cheng and Lipták in which a specific structure emerges when a graph is disconnected and often occurs in various interconnection networks. This phenomenon means that if a certain number of vertices or edges are deleted from a graph, the remaining part either stays connected or breaks into one large component along with smaller components with just a few vertices. This phenomenon can be observed in many types of graphs and has important implications for network analysis and optimization. In this paper, we first validate the phenomenon of linearly many faults for surviving graph of a burnt pancake graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> when removing any edge subset with a size of approximately six times <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>λ</mi><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula>. For graph <i>G</i>, the <i>ℓ</i>-component edge connectivity denoted as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mi>ℓ</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> (resp., the <i>ℓ</i>-extra edge connectivity denoted as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>λ</mi><mrow><mo>(</mo><mi>ℓ</mi><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>) is the cardinality of a minimum edge subset <i>S</i> such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>S</mi></mrow></semantics></math></inline-formula> is disconnected and has at least <i>ℓ</i> components (resp., each component of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>S</mi></mrow></semantics></math></inline-formula> has at least <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ℓ</mi><mo>+</mo><mn>1</mn></mrow></semantics></math></inline-formula> vertices). Both <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mi>ℓ</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> and e<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>λ</mi><mrow><mo>(</mo><mi>ℓ</mi><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> are essential metrics for network reliability assessment. Specifically, from the property of “linearly many faults”, we may further prove that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mn>5</mn></msub><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>=</mo><msup><mi>λ</mi><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>+</mo><mn>3</mn><mo>=</mo><mn>4</mn><mi>n</mi><mo>−</mo><mn>3</mn></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>⩾</mo><mn>5</mn></mrow></semantics></math></inline-formula>; <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mn>6</mn></msub><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>=</mo><msup><mi>λ</mi><mrow><mo>(</mo><mn>4</mn><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>+</mo><mn>4</mn><mo>=</mo><mn>5</mn><mi>n</mi><mo>−</mo><mn>4</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>λ</mi><mn>7</mn></msub><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>=</mo><msup><mi>λ</mi><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></msup><mrow><mo>(</mo><mi>B</mi><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>+</mo><mn>5</mn><mo>=</mo><mn>6</mn><mi>n</mi><mo>−</mo><mn>5</mn></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>⩾</mo><mn>6</mn></mrow></semantics></math></inline-formula>.https://www.mdpi.com/2227-7390/12/2/268burnt pancake graphcomponent edge connectivityextra edge connectivitylinearly many faultsconditional connectivity |
| spellingShingle | Mei-Mei Gu Hong-Xia Yan Jou-Ming Chang A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications Mathematics burnt pancake graph component edge connectivity extra edge connectivity linearly many faults conditional connectivity |
| title | A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications |
| title_full | A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications |
| title_fullStr | A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications |
| title_full_unstemmed | A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications |
| title_short | A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications |
| title_sort | validation of the phenomenon of linearly many faults on burnt pancake graphs with its applications |
| topic | burnt pancake graph component edge connectivity extra edge connectivity linearly many faults conditional connectivity |
| url | https://www.mdpi.com/2227-7390/12/2/268 |
| work_keys_str_mv | AT meimeigu avalidationofthephenomenonoflinearlymanyfaultsonburntpancakegraphswithitsapplications AT hongxiayan avalidationofthephenomenonoflinearlymanyfaultsonburntpancakegraphswithitsapplications AT joumingchang avalidationofthephenomenonoflinearlymanyfaultsonburntpancakegraphswithitsapplications AT meimeigu validationofthephenomenonoflinearlymanyfaultsonburntpancakegraphswithitsapplications AT hongxiayan validationofthephenomenonoflinearlymanyfaultsonburntpancakegraphswithitsapplications AT joumingchang validationofthephenomenonoflinearlymanyfaultsonburntpancakegraphswithitsapplications |