<i>k</i>-Path-Connectivity of Completely Balanced Tripartite Graphs
For a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)&l...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-06-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/11/6/270 |
| _version_ | 1797490012430794752 |
|---|---|
| author | Pi Wang Shasha Li Xiaoxue Gao |
| author_facet | Pi Wang Shasha Li Xiaoxue Gao |
| author_sort | Pi Wang |
| collection | DOAJ |
| description | For a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> and a set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>⊆</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a size at least 2, a path in <i>G</i> is said to be an <i>S</i>-path if it connects all vertices of <i>S</i>. Two <i>S</i>-paths <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mn>1</mn></msub></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mn>2</mn></msub></semantics></math></inline-formula> are said to be <i>internally disjoint</i> if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>E</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>1</mn></msub><mo>)</mo></mrow><mo>∩</mo><mi>E</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>2</mn></msub><mo>)</mo></mrow><mo>=</mo><mo>∅</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>1</mn></msub><mo>)</mo></mrow><mo>∩</mo><mi>V</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>2</mn></msub><mo>)</mo></mrow><mo>=</mo><mi>S</mi></mrow></semantics></math></inline-formula>; that is, they share no vertices and edges apart from <i>S</i>. Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> denote the maximum number of internally disjoint <i>S</i>-paths in <i>G</i>. The <i>k</i>-path-connectivity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of <i>G</i> is then defined as the minimum <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <i>S</i> ranges over all <i>k</i>-subsets of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>. In this paper, we study the <i>k</i>-path-connectivity of the complete balanced tripartite graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mrow><mi>n</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> and obtain <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>k</mi></msub><mfenced separators="" open="(" close=")"><msub><mi>K</mi><mrow><mi>n</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>n</mi></mrow></msub></mfenced><mo>=</mo><mfenced separators="" open="⌊" close="⌋"><mfrac><mrow><mn>2</mn><mi>n</mi></mrow><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></mfrac></mfenced></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>3</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi><mo>.</mo></mrow></semantics></math></inline-formula> |
| first_indexed | 2024-03-10T00:25:51Z |
| format | Article |
| id | doaj.art-9440f30ab7424b95a347fe2cd42a6768 |
| institution | Directory Open Access Journal |
| issn | 2075-1680 |
| language | English |
| last_indexed | 2024-03-10T00:25:51Z |
| publishDate | 2022-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Axioms |
| spelling | doaj.art-9440f30ab7424b95a347fe2cd42a67682023-11-23T15:35:14ZengMDPI AGAxioms2075-16802022-06-0111627010.3390/axioms11060270<i>k</i>-Path-Connectivity of Completely Balanced Tripartite GraphsPi Wang0Shasha Li1Xiaoxue Gao2School of Mathematics and Statistics, Ningbo University, Ningbo 315211, ChinaSchool of Mathematics and Statistics, Ningbo University, Ningbo 315211, ChinaSchool of Mathematics and Statistics, Ningbo University, Ningbo 315211, ChinaFor a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> and a set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>S</mi><mo>⊆</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a size at least 2, a path in <i>G</i> is said to be an <i>S</i>-path if it connects all vertices of <i>S</i>. Two <i>S</i>-paths <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mn>1</mn></msub></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mn>2</mn></msub></semantics></math></inline-formula> are said to be <i>internally disjoint</i> if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>E</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>1</mn></msub><mo>)</mo></mrow><mo>∩</mo><mi>E</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>2</mn></msub><mo>)</mo></mrow><mo>=</mo><mo>∅</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>1</mn></msub><mo>)</mo></mrow><mo>∩</mo><mi>V</mi><mrow><mo>(</mo><msub><mi>P</mi><mn>2</mn></msub><mo>)</mo></mrow><mo>=</mo><mi>S</mi></mrow></semantics></math></inline-formula>; that is, they share no vertices and edges apart from <i>S</i>. Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> denote the maximum number of internally disjoint <i>S</i>-paths in <i>G</i>. The <i>k</i>-path-connectivity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>k</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of <i>G</i> is then defined as the minimum <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <i>S</i> ranges over all <i>k</i>-subsets of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>. In this paper, we study the <i>k</i>-path-connectivity of the complete balanced tripartite graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mrow><mi>n</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>n</mi></mrow></msub></semantics></math></inline-formula> and obtain <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>π</mi><mi>k</mi></msub><mfenced separators="" open="(" close=")"><msub><mi>K</mi><mrow><mi>n</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>n</mi></mrow></msub></mfenced><mo>=</mo><mfenced separators="" open="⌊" close="⌋"><mfrac><mrow><mn>2</mn><mi>n</mi></mrow><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></mfrac></mfenced></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>3</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi><mo>.</mo></mrow></semantics></math></inline-formula>https://www.mdpi.com/2075-1680/11/6/270path-connectivityinternally disjoint pathscomplete balanced tripartite graphs |
| spellingShingle | Pi Wang Shasha Li Xiaoxue Gao <i>k</i>-Path-Connectivity of Completely Balanced Tripartite Graphs Axioms path-connectivity internally disjoint paths complete balanced tripartite graphs |
| title | <i>k</i>-Path-Connectivity of Completely Balanced Tripartite Graphs |
| title_full | <i>k</i>-Path-Connectivity of Completely Balanced Tripartite Graphs |
| title_fullStr | <i>k</i>-Path-Connectivity of Completely Balanced Tripartite Graphs |
| title_full_unstemmed | <i>k</i>-Path-Connectivity of Completely Balanced Tripartite Graphs |
| title_short | <i>k</i>-Path-Connectivity of Completely Balanced Tripartite Graphs |
| title_sort | i k i path connectivity of completely balanced tripartite graphs |
| topic | path-connectivity internally disjoint paths complete balanced tripartite graphs |
| url | https://www.mdpi.com/2075-1680/11/6/270 |
| work_keys_str_mv | AT piwang ikipathconnectivityofcompletelybalancedtripartitegraphs AT shashali ikipathconnectivityofcompletelybalancedtripartitegraphs AT xiaoxuegao ikipathconnectivityofcompletelybalancedtripartitegraphs |