Graph Theory with Applications

A special issue of Axioms (ISSN 2075-1680).

Deadline for manuscript submissions: closed (30 June 2022) | Viewed by 36032

Special Issue Editors

Center for Combinatorics, Nankai University, Tianjin 300071, China
Interests: graph theory and its applications; combinatorial optimizations; algorithms and complexity analysis; NP-hard problems; discrete mathematics and its applications in computer science, chemistry, biology, etc.
Special Issues, Collections and Topics in MDPI journals
School of Mathematical Sciences, Nankai University, Tianjin 300071, China
Interests: graph theory; combinatorial optimizations; discrete mathematics and combinatorics, etc.

Special Issue Information

Dear Colleagues,

Graph theory can be traced back to 1735, when Leonhard Euler presented his solution of the Königsberg seven bridge problem. With the triumph in computer-aided resolution of the four color conjecture by Appel and Haken in 1977, graph theory entered a new era. In the past several decades, due to the increasing demands from applied sciences and other branches of mathematics, graph theory has had a dramatic development and become a flourishing discipline, including but not limited to the following subjects: algebraic graph theory, algorithmic graph theory, chemical graph theory, extremal graph theory, random graph theory, spectral graph theory, structural graph theory, topological graph theory, etc.

In this Special Issue, we would like to invite you to submit your recent research in the area of graph theory and its applications. Submissions related to all aspects of graph theory and its applications that present new theoretical results or algorithms are welcome.

Prof. Dr. Xueliang Li
Dr. Jiaao Li
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Axioms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2400 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • graph theory
  • applications of graph theory
  • cayley graphs
  • chemical graphs
  • colored graphs
  • connectivity
  • digraphs
  • distance regular graphs
  • eigenvalues of graphs
  • Eulerian and Hamiltonian graphs
  • extremal problems in graphs
  • flows in graphs
  • graph algorithms and complexity analysis
  • graph coloring
  • graph embedding
  • graph parameters
  • graph polynomials
  • hypergraphs
  • matching
  • NP-hard problems in graphs
  • paths and cycles
  • planar graphs
  • Ramsey problems
  • random graphs
  • Turán problems

Published Papers (22 papers)

Order results
Result details
Select all
Export citation of selected articles as:

Research

17 pages, 8032 KiB  
Article
Assessing Graph Robustness through Modified Zagreb Index
by Rui Chen, Jianping Li and Weihua He
Axioms 2022, 11(9), 484; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11090484 - 19 Sep 2022
Viewed by 1272
Abstract
Graph robustness or network robustness is the ability that a graph or a network preserves its connectivity or other properties after the loss of vertices and edges, which has been a central problem in the research of complex networks. In this paper, we [...] Read more.
Graph robustness or network robustness is the ability that a graph or a network preserves its connectivity or other properties after the loss of vertices and edges, which has been a central problem in the research of complex networks. In this paper, we introduce the Modified Zagreb index and Modified Zagreb index centrality as novel measures to study graph robustness. We theoretically find some relationships between these novel measures and some other graph measures. Then, we use Modified Zagreb index centrality to analyze the robustness of BA scale-free networks, ER random graphs and WS small world networks under deliberate or random vertex attacks. We also study the correlations between this new measure and some other existed measures. Finally, we use Modified Zagreb index centrality to study the robustness of two real world networks. All these results demonstrate the efficiency of Modified Zagreb index centrality for assessing the graph robustness. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

14 pages, 335 KiB  
Article
The Independence Number Conditions for 2-Factors of a Claw-Free Graph
by Wanpeng Lei, Liming Xiong and Jun Yin
Axioms 2022, 11(8), 417; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11080417 - 19 Aug 2022
Viewed by 1029
Abstract
In 2014, some scholars showed that every 2-connected claw-free graph G with independence number α(G)3 is Hamiltonian with one exception of family of graphs. If a nontrivial path contains only internal vertices of degree two and end vertices [...] Read more.
In 2014, some scholars showed that every 2-connected claw-free graph G with independence number α(G)3 is Hamiltonian with one exception of family of graphs. If a nontrivial path contains only internal vertices of degree two and end vertices of degree not two, then we call it a branch. A set S of branches of a graph G is called a branch cut if we delete all edges and internal vertices of branches of S leading to more components than G. We use a branch bond to denote a minimal branch cut. If a branch-bond has an odd number of branches, then it is called odd. In this paper, we shall characterize all 2-connected claw-free graphs G such that every odd branch-bond of G has an edge branch and such that α(G)5 but has no 2-factor. We also consider the same problem for those 2-edge-connected claw-free graphs with α(G)4. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

12 pages, 748 KiB  
Article
On the Chromatic Index of the Signed Generalized Petersen Graph GP(n,2)
by Shanshan Zheng, Hongyan Cai, Yuanpei Wang and Qiang Sun
Axioms 2022, 11(8), 393; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11080393 - 10 Aug 2022
Viewed by 1285
Abstract
Let G be a graph and σ:E(G){+1,1} be a mapping. The pair (G,σ), denoted by Gσ, is called a signed graph. A (proper) [...] Read more.
Let G be a graph and σ:E(G){+1,1} be a mapping. The pair (G,σ), denoted by Gσ, is called a signed graph. A (proper) l-edge coloring γ of Gσ is a mapping from each vertex–edge incidence of Gσ to Mq such that γ(v,e)=σ(e)γ(w,e) for each edge e=vw, and no two vertex–edge incidences have the same color; that is, γ(v,e)γ(v,f). The chromatic index is the minimal number q such that Gσ has a proper q-edge coloring, denoted by χ(Gσ). In 2020, Behr proved that the chromatic index of a signed graph is its maximum degree or maximum plus one. In this paper, we considered the chromatic index of the signed generalized Petersen graph GP(n,2) and show that its chromatic index is its maximum degree for most cases. In detail, we proved that (1) χ(GPσ(n,2))=3 if n3 mod 6(n9); (2) χ(GPσ(n,2))=3 if n=2p(p4). Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

14 pages, 292 KiB  
Article
Enumeration of the Additive Degree–Kirchhoff Index in the Random Polygonal Chains
by Xianya Geng and Wanlin Zhu
Axioms 2022, 11(8), 373; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11080373 - 28 Jul 2022
Viewed by 1103
Abstract
The additive degree–Kirchhoff index is an important topological index. This paper we devote to establishing the explicit analytical expression for the simple formulae of the expected value of the additive degree–Kirchhoff index in a random polygon. Based on the result above, the additive [...] Read more.
The additive degree–Kirchhoff index is an important topological index. This paper we devote to establishing the explicit analytical expression for the simple formulae of the expected value of the additive degree–Kirchhoff index in a random polygon. Based on the result above, the additive degree–Kirchhoff indexes of all polygonal chains with extremal values and average values are obtained. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

12 pages, 295 KiB  
Article
ISI-Equienergetic Graphs
by Qingfang Ye and Fengwei Li
Axioms 2022, 11(8), 372; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11080372 - 28 Jul 2022
Cited by 2 | Viewed by 1104
Abstract
The ISI-energy εisi(G) of a graph G=(V,E) is the sum of the absolute values of the eigenvalues of the ISI-matrix [...] Read more.
The ISI-energy εisi(G) of a graph G=(V,E) is the sum of the absolute values of the eigenvalues of the ISI-matrix C(G)=[cij]n×n in which cij=d(vi)d(vj)d(vi)+d(vj) if vivjE(G) and cij=0 otherwise. d(vi) denotes the degree of vertex viV. As a class of graph energy, ISI-energy can be utilized to ascertain the general energy of conjugated carbon molecules. Two non-isomorphic graphs of the same order are said to be ISI-equienergetic if their ISI-energies are equal. In this paper, we construct pairs of connected, ISI-noncospectral, ISI-equienergetic graphs of order n for all n9. In addition, for n-vertex r(r3)-regular graph G, and for each k2, we obtain εisi(Lk(G)¯), depending only on n and r. This result enables a systematic construction of pairs of ISI-noncospectral graphs of the same order, having equal ISI-energies. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

18 pages, 339 KiB  
Article
On the Laplacian, the Kirchhoff Index, and the Number of Spanning Trees of the Linear Pentagonal Derivation Chain
by Yue Tu, Xiaoling Ma, Yuqing Zhang and Junyu Ren
Axioms 2022, 11(6), 278; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11060278 - 09 Jun 2022
Cited by 2 | Viewed by 1538
Abstract
Let Pn be a pentagonal chain with 2n pentagons in which two pentagons with two edges in common can be regarded as adding one vertex and two edges to a hexagon. Thus, the linear pentagonal derivation chains QPn represent [...] Read more.
Let Pn be a pentagonal chain with 2n pentagons in which two pentagons with two edges in common can be regarded as adding one vertex and two edges to a hexagon. Thus, the linear pentagonal derivation chains QPn represent the graph obtained by attaching four-membered rings to every two pentagons of Pn. In this article, the Laplacian spectrum of QPn consisting of the eigenvalues of two symmetric matrices is determined. Next, the formulas for two graph invariants that can be represented by the Laplacian spectrum, namely, the Kirchhoff index and the number of spanning trees, are studied. Surprisingly, the Kirchhoff index is almost one half of the Wiener index of a linear pentagonal derivation chain QPn. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

7 pages, 440 KiB  
Article
Super Connected Direct Product of Graphs and Cycles
by Jiaqiong Yin and Yingzhi Tian
Axioms 2022, 11(6), 277; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11060277 - 09 Jun 2022
Viewed by 1454
Abstract
The topology of an interconnection network can be modeled by a graph G=(V(G),E(G)). The connectivity of graph G is a parameter used to measure the reliability of a corresponding network. [...] Read more.
The topology of an interconnection network can be modeled by a graph G=(V(G),E(G)). The connectivity of graph G is a parameter used to measure the reliability of a corresponding network. The direct product is an important graph product. This paper mainly focuses on the super connectedness of the direct product of graphs and cycles. The connectivity of G, denoted by κ(G), is the size of a minimum vertex set SV(G) such that GS is not connected or has only one vertex. The graph G is said to be super connected, simply super-κ, if every minimum vertex cut is the neighborhood of a vertex with minimum degree. The direct product of two graphs G and H, denoted by G×H, is the graph with vertex set V(G×H)=V(G)×V(H) and edge set E(G×H)={(u1,v1)(u2,v2)|u1u2E(G),v1v2E(H)}. In this paper, we give some sufficient conditions for the direct product G×Cn to be super connected, where Cn is the cycle on n vertices. Furthermore, those sufficient conditions are the best possible. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

6 pages, 252 KiB  
Article
k-Path-Connectivity of Completely Balanced Tripartite Graphs
by Pi Wang, Shasha Li and Xiaoxue Gao
Axioms 2022, 11(6), 270; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11060270 - 05 Jun 2022
Cited by 1 | Viewed by 1471
Abstract
For a graph G=(V,E) and a set SV(G) of a size at least 2, a path in G is said to be an S-path if it connects all vertices of S [...] Read more.
For a graph G=(V,E) and a set SV(G) of a size at least 2, a path in G is said to be an S-path if it connects all vertices of S. Two S-paths P1 and P2 are said to be internally disjoint if E(P1)E(P2)= and V(P1)V(P2)=S; that is, they share no vertices and edges apart from S. Let πG(S) denote the maximum number of internally disjoint S-paths in G. The k-path-connectivity πk(G) of G is then defined as the minimum πG(S), where S ranges over all k-subsets of V(G). In this paper, we study the k-path-connectivity of the complete balanced tripartite graph Kn,n,n and obtain πkKn,n,n=2nk1 for 3kn. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
14 pages, 377 KiB  
Article
The Expected Value of Hosoya Index and Merrifield–Simmons Index in a Random Cyclooctylene Chain
by Yushuang Sun and Xianya Geng
Axioms 2022, 11(6), 261; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11060261 - 30 May 2022
Cited by 1 | Viewed by 1230
Abstract
The Hosoya index m(G) and the Merrifield–Simmons index i(G) of a graph G are the number of matchings and the number of independent sets in G. In this paper, we establish exact formulas for the expected [...] Read more.
The Hosoya index m(G) and the Merrifield–Simmons index i(G) of a graph G are the number of matchings and the number of independent sets in G. In this paper, we establish exact formulas for the expected value of the Hosoya index and Merrifield–Simmons index of the random cyclooctylene chains, which are graphs of a chemical chain consisting of n octagons, each of which is connected to the end of the previous octagon by an edge. In addition, we obtain the expected values and the average values of the two indexes through the relevant chemical diagrams and a series of accurate formulas with respect to the set of all cyclooctylene chains with n octagons. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

16 pages, 484 KiB  
Article
Spectral Invariants and Their Application on Spectral Characterization of Graphs
by Jun Yin, Haixing Zhao and Sun Xie
Axioms 2022, 11(6), 260; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11060260 - 29 May 2022
Cited by 1 | Viewed by 1242
Abstract
In this paper, we give a method to characterize graphs determined by their adjacency spectrum. At first, we give two parameters Π1(G) and Π2(G), which are related to coefficients of the characteristic polynomial of [...] Read more.
In this paper, we give a method to characterize graphs determined by their adjacency spectrum. At first, we give two parameters Π1(G) and Π2(G), which are related to coefficients of the characteristic polynomial of graph G. All connected graphs with Π1(G){1,0,1,2,3} and Π2(G){0,1,2,3} are characterized. Some interesting properties of Π1(G) and Π2(G) are also given. We then find the necessary and sufficient conditions for two classes of graphs to be determined by their adjacency spectrum. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

7 pages, 287 KiB  
Article
Total Rainbow Connection Number of Some Graph Operations
by Hengzhe Li, Yingbin Ma and Yan Zhao
Axioms 2022, 11(6), 254; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11060254 - 26 May 2022
Viewed by 1449
Abstract
In a graph H with a total coloring, a path Q is a total rainbow if all elements in V(Q)E(Q), except for its end vertices, are assigned different colors. The total coloring of a [...] Read more.
In a graph H with a total coloring, a path Q is a total rainbow if all elements in V(Q)E(Q), except for its end vertices, are assigned different colors. The total coloring of a graph H is a total rainbow connected coloring if, for any x,yV(H), there is a total rainbow path joining them. The total rainbow connection number trc(H) of H is the minimum integer r such that there is a total rainbow-connected coloring of H using r colors. In this paper, we study the total rainbow connection number of several graph operations (specifically, adding an edge, deleting an edge, and the Cartesian product) for which the total rainbow connection number is upper-bounded by a linear function of its radius. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

6 pages, 499 KiB  
Article
Edge Neighbor Toughness of Graphs
by Xin Feng, Zongtian Wei and Yucheng Yang
Axioms 2022, 11(6), 248; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11060248 - 25 May 2022
Cited by 1 | Viewed by 1277
Abstract
A new graph parameter, edge neighbor toughness is introduced to measure how difficult it is for a graph to be broken into many components through the deletion of the closed neighborhoods of a few edges. Let G=(V,E) [...] Read more.
A new graph parameter, edge neighbor toughness is introduced to measure how difficult it is for a graph to be broken into many components through the deletion of the closed neighborhoods of a few edges. Let G=(V,E) be a graph. An edge e is said to be subverted when its neighborhood and the two endvertices are deleted from G. An edge set SE(G) is called an edge cut-strategy if all the edges in S has been subverted from G and the survival subgraph, denoted by G/S, is disconnected, or is a single vertex, or is. The edge neighbor toughness of a graph G is defined to be tEN(G)=minSE(G){|S|c(G/S)}, where S is any edge cut strategy of G, c(G/S) is the number of the components of G/S. In this paper, the properties of this parameter are investigated, and the proof of the computation problem of edge neighbor toughness is NP-complete; finally, a polynomial algorithm for computing the edge neighbor toughness of trees is given. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

20 pages, 347 KiB  
Article
Some New Bounds for the Inverse Sum Indeg Energy of Graphs
by Fengwei Li, Qingfang Ye and Hajo Broersma
Axioms 2022, 11(5), 243; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11050243 - 23 May 2022
Cited by 4 | Viewed by 1528
Abstract
Let G be a (molecular) graph with n vertices, and di be the degree of its i-th vertex. Then, the inverse sum indeg matrix of G is the n×n matrix C(G) with entries [...] Read more.
Let G be a (molecular) graph with n vertices, and di be the degree of its i-th vertex. Then, the inverse sum indeg matrix of G is the n×n matrix C(G) with entries cij=didjdi+dj, if the i-th and the j-th vertices are adjacent and 0 otherwise. Let μ1μ2μn be the eigenvalues of C arranged in order. The inverse sum indeg energy of G, εisi(G) can be represented as j=1n|μi|. In this paper, we establish several novel upper and lower sharp bounds on μ1 and εisi(G) via some other graph parameters, and describe the structures of the extremal graphs. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
7 pages, 287 KiB  
Article
Characterizing Forbidden Pairs for the Edge-Connectivity of a Connected Graph to Be Its Minimum Degree
by Junfeng Du, Ziwen Huang and Liming Xiong
Axioms 2022, 11(5), 219; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11050219 - 09 May 2022
Cited by 1 | Viewed by 1567
Abstract
Let H be a class of given graphs. A graph G is said to be H-free if G contains no induced copies of H for any HH. In this article, we characterize all connected subgraph pairs [...] Read more.
Let H be a class of given graphs. A graph G is said to be H-free if G contains no induced copies of H for any HH. In this article, we characterize all connected subgraph pairs {R,S} guranteeing the edge-connectivity of a connected {R,S}-free graph to have the same minimum degree. Our result is a supplement of Wang et al. Furthermore, we obtain a relationship of forbidden sets when those general parameters have the recurrence relation. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

6 pages, 238 KiB  
Article
Randić Index of a Line Graph
by Jiangfu Zhang and Baoyindureng Wu
Axioms 2022, 11(5), 210; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11050210 - 29 Apr 2022
Cited by 6 | Viewed by 2032
Abstract
The Randić index of a graph G, denoted by R(G), is defined as the sum of 1/d(u)d(v) for all edges uv of G, where [...] Read more.
The Randić index of a graph G, denoted by R(G), is defined as the sum of 1/d(u)d(v) for all edges uv of G, where d(u) denotes the degree of a vertex u in G. In this note, we show that R(L(T))>n4 for any tree T of order n3. A number of relevant conjectures are proposed. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

13 pages, 342 KiB  
Article
A Survey on the k-Path Vertex Cover Problem
by Jianhua Tu
Axioms 2022, 11(5), 191; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11050191 - 20 Apr 2022
Cited by 1 | Viewed by 1988
Abstract
Given an integer k ≥ 2, a k-path is a path on k vertices. A set of vertices in a graph G is called a k-path vertex cover if it includes at least one vertex of every k-path of G. [...] Read more.
Given an integer k ≥ 2, a k-path is a path on k vertices. A set of vertices in a graph G is called a k-path vertex cover if it includes at least one vertex of every k-path of G. A minimum k-path vertex cover in G is a k-path vertex cover having the smallest possible number of vertices and its cardinality is called the k-path vertex cover number of G. In the k-path vertex cover problem, the goal is to find a minimum k-path vertex cover in a given graph. In this paper, we present a brief survey of the current state of the art in the study of the k-path vertex cover problem and the k-path vertex cover number. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
7 pages, 277 KiB  
Article
Strong Chromatic Index of Outerplanar Graphs
by Ying Wang, Yiqiao Wang, Weifan Wang and Shuyu Cui
Axioms 2022, 11(4), 168; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11040168 - 08 Apr 2022
Cited by 1 | Viewed by 1556
Abstract
The strong chromatic index χs(G) of a graph G is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in G. It was proved In 2013, that every [...] Read more.
The strong chromatic index χs(G) of a graph G is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in G. It was proved In 2013, that every outerplanar graph G with Δ3 has χs(G)3Δ3. In this paper, we give a characterization for an outerplanar graph G to have χs(G)=3Δ3. We also show that if G is a bipartite outerplanar graph, then χs(G)2Δ; and χs(G)=2Δ if and only if G contains a particular subgraph. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

15 pages, 553 KiB  
Article
The Spectral Distribution of Random Mixed Graphs
by Yue Guan, Bo Cheng, Minfeng Chen, Meili Liang, Jianxi Liu, Jinxun Wang, Chao Yang and Li Zeng
Axioms 2022, 11(3), 126; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11030126 - 11 Mar 2022
Viewed by 1676
Abstract
In this work, we propose a random mixed graph model Gn(p(n),q(n)) that incorporates both the classical Erdős-Rényi’s random graph model and the random oriented graph model. We show that the empirical [...] Read more.
In this work, we propose a random mixed graph model Gn(p(n),q(n)) that incorporates both the classical Erdős-Rényi’s random graph model and the random oriented graph model. We show that the empirical spectral distribution of Gn(p(n),q(n)) converges to the standard semicircle law under some mild condition, and the Monte Carlo simulation highly agrees with our result. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

18 pages, 369 KiB  
Article
The Local Antimagic Total Chromatic Number of Some Wheel-Related Graphs
by Xue Yang, Hong Bian, Haizheng Yu and Dandan Liu
Axioms 2022, 11(3), 97; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11030097 - 25 Feb 2022
Viewed by 2035
Abstract
Let G=(V,E) be a connected graph with |V|=n and |E|=m. A bijection [...] Read more.
Let G=(V,E) be a connected graph with |V|=n and |E|=m. A bijection f:V(G)E(G){1,2,,n+m} is called local antimagic total labeling if, for any two adjacent vertices u and v, ωt(u)ωt(v), where ωt(u)=f(u)+eE(u)f(e), and E(u) is the set of edges incident to u. Thus, any local antimagic total labeling induces a proper coloring of G, where the vertex x in G is assigned the color ωt(x). The local antimagic total chromatic number, denoted by χlat(G), is the minimum number of colors taken over all colorings induced by local antimagic total labelings of G. In this paper, we present the local antimagic total chromatic numbers of some wheel-related graphs, such as the fan graph Fn, the bowknot graph Bn,n, the Dutch windmill graph D4n, the analogous Dutch graph AD4n and the flower graph Fn. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

11 pages, 446 KiB  
Article
Local Optimality of Mixed Reliability for Several Classes of Networks with Fixed Sizes
by Lixin Dong, Haixing Zhao and Hong-Jian Lai
Axioms 2022, 11(3), 91; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11030091 - 24 Feb 2022
Viewed by 1347
Abstract
In this work, the local optimality of mixed reliability of networks is surveyed. A reliability comparison criterion related with subgraphs to measure the local optimality of the mixed reliability of networks is established. Using the comparison criterion, we characterize all locally optimally mixed [...] Read more.
In this work, the local optimality of mixed reliability of networks is surveyed. A reliability comparison criterion related with subgraphs to measure the local optimality of the mixed reliability of networks is established. Using the comparison criterion, we characterize all locally optimally mixed reliable networks among all n-vertex networks with fixed sizes m=n, m=n+1 and m=n+2, respectively. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

8 pages, 259 KiB  
Article
A New Proof for a Result on the Inclusion Chromatic Index of Subcubic Graphs
by Lily Chen and Yanyi Li
Axioms 2022, 11(1), 33; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11010033 - 17 Jan 2022
Cited by 17 | Viewed by 1841
Abstract
Let G be a graph with a minimum degree δ of at least two. The inclusion chromatic index of G, denoted by χ(G), is the minimum number of colors needed to properly color the edges of [...] Read more.
Let G be a graph with a minimum degree δ of at least two. The inclusion chromatic index of G, denoted by χ(G), is the minimum number of colors needed to properly color the edges of G so that the set of colors incident with any vertex is not contained in the set of colors incident to any of its neighbors. We prove that every connected subcubic graph G with δ(G)2 either has an inclusion chromatic index of at most six, or G is isomorphic to K^2,3, where its inclusion chromatic index is seven. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

9 pages, 1220 KiB  
Article
Graph Entropy Based on Strong Coloring of Uniform Hypergraphs
by Lusheng Fang, Bo Deng, Haixing Zhao and Xiaoyun Lv
Axioms 2022, 11(1), 3; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms11010003 - 22 Dec 2021
Cited by 1 | Viewed by 2049
Abstract
The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being [...] Read more.
The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being different from the classical graph entropy, we extend this concept to a hypergraph. Then, we define the graph entropy based on the vertex strong coloring of a hypergraph. Moreover, some tightly upper and lower bounds of such graph entropies as well as the corresponding extremal hypergraphs are obtained. Full article
(This article belongs to the Special Issue Graph Theory with Applications)
Show Figures

Figure 1

Back to TopTop