Submit to Special Issue Submit Abstract to Special Issue Review for Axioms Propose a Special Issue

Journal Menu

Journal Browser

► Journal Browser

Advances in Graph Theory and Combinatorial Optimization

Special Issue Editors
Special Issue Information
Keywords
Published Papers

A special issue of Axioms (ISSN 2075-1680). This special issue belongs to the section "Algebra and Number Theory".

Deadline for manuscript submissions: 31 July 2024 | Viewed by 7088

Share This Special Issue

Special Issue Editors

Prof. Dr. Xueliang Li

E-Mail Website
Guest Editor

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

Dr. Weihua He

E-Mail Website
Guest Editor

School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou 510520, China
Interests: graph theory; combinatorial optimizations; algorithm; machine learning

Special Issue Information

Dear Colleagues,

Graph theory, which is the study of relationships between edges and vertices, is one of the most important domains in mathematics and computer science. Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Graph theory and combinatorial optimization have many related research problems and are two closely related research fields. In particular, many graph theorists are working on combinatorial optimization problems arising from graph theoretical problems, and algorithmic graph theory represents a very popular topic in this field. Recently, there have been considerable developments in graph theory and combinatorial optimization both from a theoretical and application point of view.

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

Prof. Dr. Xueliang Li
Dr. Weihua He
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
applied graph theory
combinatorial optimization
graph algorithms and complexity analysis
NP-hard problems in graphs
optimization theory
Eulerian and Hamiltonian graphs
extremal problems in graphs
graph parameters
graphical indices
paths and cycles
matchings
connectivity
Ramsey problems
Turán problems
flows in graphs
graph colouring
graph embedding
random graphs
planar graphs
chemical graph theory
various graph polynomials
eigenvalues of graphs
distance regular graphs
digraphs
hypergraphs

Published Papers (7 papers)

Download All Papers

Research

11 pages, 278 KiB

Open AccessArticle

The Restricted Edge-Connectivity of Strong Product Graphs

by Hazhe Ye and Yingzhi Tian

Axioms 2024, 13(4), 231; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms13040231 - 31 Mar 2024

Viewed by 483

Abstract

The restricted edge-connectivity of a connected graph G, denoted by

λ^{'} (G)

, if it exists, is the minimum cardinality of a set of edges whose deletion makes G disconnected, and each component has at least two vertices. It [...] Read more.

The restricted edge-connectivity of a connected graph G, denoted by

λ^{'} (G)

, if it exists, is the minimum cardinality of a set of edges whose deletion makes G disconnected, and each component has at least two vertices. It was proved that

λ^{'} (G)

exists if and only if G has at least four vertices and G is not a star. In this case, a graph G is called maximally restricted edge-connected if

λ^{'} (G) = ξ (G)

, and a graph G is called super restricted edge-connected if each minimum restricted edge-cut isolates an edge of G. The strong product of graphs G and H, denoted by

G ⊠ H

, is the graph with the vertex set

V (G) \times V (H)

and the edge set

{(x_{1}, y_{1}) (x_{2}, y_{2}) | x_{1} = x_{2}

and

y_{1} y_{2} \in E (H)

; or

y_{1} = y_{2}

and

x_{1} x_{2} \in E (G)

; or

x_{1} x_{2} \in E (G)

and

y_{1} y_{2} \in E (H)

}. In this paper, we determine, for any nontrivial connected graph G, the restricted edge-connectivity of

G ⊠ P_{n}

G ⊠ C_{n}

and

G ⊠ K_{n}

, where

P_{n}

C_{n}

and

K_{n}

are the path, cycle and complete graph of order n, respectively. As corollaries, we give sufficient conditions for these strong product graphs

G ⊠ P_{n}

G ⊠ C_{n}

and

G ⊠ K_{n}

to be maximally restricted edge-connected and super restricted edge-connected. Full article

(This article belongs to the Special Issue Advances in Graph Theory and Combinatorial Optimization)

► Show Figures

Figure 1

12 pages, 245 KiB

Open AccessArticle

Extremal Sombor Index of Graphs with Cut Edges and Clique Number

by Mihrigul Wali and Raxida Guji

Axioms 2024, 13(1), 66; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms13010066 - 20 Jan 2024

Viewed by 743

Abstract

The Sombor index is defined as

S O (G) = \sum_{u v \in E (G)} \sqrt{d^{2} (u) + d^{2} (v)}

, where

d (u)

and

d (v)

represent [...] Read more.

The Sombor index is defined as

S O (G) = \sum_{u v \in E (G)} \sqrt{d^{2} (u) + d^{2} (v)}

, where

d (u)

and

d (v)

represent the number of edges in the graph G connected to the vertices u and v, respectively. In this paper, we characterize the largest and second largest Sombor indexes with a given number of cut edges. Moreover, we determine the upper and lower sharp bounds of the Sombor index with a given number of clique numbers, and we characterize the extremal graphs. Full article

(This article belongs to the Special Issue Advances in Graph Theory and Combinatorial Optimization)

► Show Figures

Figure 1

16 pages, 321 KiB

Open AccessArticle

Entropy and Multi-Fractal Analysis in Complex Fractal Systems Using Graph Theory

by Zeeshan Saleem Mufti, Ali H. Tedjani, Rukhshanda Anjum and Turki Alsuraiheed

Axioms 2023, 12(12), 1126; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms12121126 - 15 Dec 2023

Viewed by 824

Abstract

In 1997, Sierpinski graphs,

S (n, k)

, were obtained by Klavzar and Milutinovic. The graph

S (1, k)

represents the complete graph

K_{k}

and

S (n, 3)

is known as the graph [...] Read more.

In 1997, Sierpinski graphs,

S (n, k)

, were obtained by Klavzar and Milutinovic. The graph

S (1, k)

represents the complete graph

K_{k}

and

S (n, 3)

is known as the graph of the Tower of Hanoi. Through generalizing the notion of a Sierpinski graph, a graph named a generalized Sierpinski graph, denoted by

S i e (Λ, t)

, already exists in the literature. For every graph, numerous polynomials are being studied, such as chromatic polynomials, matching polynomials, independence polynomials, and the M-polynomial. For every polynomial there is an underlying geometrical object which extracts everything that is hidden in a polynomial of a common framework. Now, we describe the steps by which we complete our task. In the first step, we generate an M-polynomial for a generalized Sierpinski graph

S i e (Λ, t)

. In the second step, we extract some degree-based indices of a generalized Sierpinski graph

S i e (Λ, t)

using the M-polynomial generated in step 1. In step 3, we generate the entropy of a generalized Sierpinski graph

S i e (Λ, t)

by using the Randić index. Full article

(This article belongs to the Special Issue Advances in Graph Theory and Combinatorial Optimization)

► Show Figures

Figure 1

15 pages, 353 KiB

Open AccessArticle

The Algebra of Signatures for Extreme Two-Uniform Hypergraphs

by Evgeniya Egorova, Aleksey Mokryakov and Vladimir Tsurkov

Axioms 2023, 12(12), 1123; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms12121123 - 15 Dec 2023

Viewed by 815

Abstract

In the last decade, several characterizations have been constructed for constructions such as extreme hypergraphs. One of the most recently described features is the signature. A signature is a number that uniquely describes an extremal and allows one to efficiently store the extremal two-uniform hypergraph itself. However, for the signature, although various algorithms have been derived for transforming it into other object-characteristics such as the base, the adjacency matrix, and the vector of vertex degrees, no isolated signature union and intersection apparatus has been constructed. This allows us to build efficient algorithms based on signatures, the most compact representation of extremal two-uniform hypergraphs. The nature of the algebraic construction that can be built on a set of signatures using union and intersection operations has also been defined. It is proved that an algebra on a set of signatures with either the union or intersection operation forms a monoid; if the algebra is defined on a set of signatures with both union and intersection operations, it forms a distributive lattice. Full article

(This article belongs to the Special Issue Advances in Graph Theory and Combinatorial Optimization)

► Show Figures

Figure 1

9 pages, 330 KiB

Open AccessArticle

Hamiltonian Indices of Three Classes of Graphs Obtained from Petersen Graph

by Shengmei Lv and Liying Zhao

Axioms 2023, 12(6), 580; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms12060580 - 11 Jun 2023

Viewed by 862

Abstract

In this paper, we mainly consider the Hamiltonian indices of three classes of graphs obtained from Petersen graph, that is, the minimum integer m of m-time iterated line graph

L^{m} (G)

of these three classes of graphs such that [...] Read more.

In this paper, we mainly consider the Hamiltonian indices of three classes of graphs obtained from Petersen graph, that is, the minimum integer m of m-time iterated line graph

L^{m} (G)

of these three classes of graphs such that

L^{m} (G)

is Hamiltonian. We show that the Hamiltonian indices of those graphs obtained by replacing every vertex of Petersen graph with a n-cycle or a complete graph of order n, or adding n pendant edges to each vertex of Petersen graph are both 2. In addition, we also study the situations of adding an edge to these three classes of graphs and obtain that their Hamiltonian indices are both 2. Full article

(This article belongs to the Special Issue Advances in Graph Theory and Combinatorial Optimization)

► Show Figures

Figure 1

12 pages, 521 KiB

Open AccessArticle

Strong Edge Coloring of K₄(t)-Minor Free Graphs

by Huixin Yin, Miaomiao Han and Murong Xu

Axioms 2023, 12(6), 556; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms12060556 - 05 Jun 2023

Viewed by 1093

Abstract

A strong edge coloring of a graph G is a proper coloring of edges in G such that any two edges of distance at most 2 are colored with distinct colors. The strong chromatic index

χ_{s}^{'} (G)

is the [...] Read more.

A strong edge coloring of a graph G is a proper coloring of edges in G such that any two edges of distance at most 2 are colored with distinct colors. The strong chromatic index

χ_{s}^{'} (G)

is the smallest integer l such that G admits a strong edge coloring using l colors. A

K_{4} (t)

-minor free graph is a graph that does not contain

K_{4} (t)

as a contraction subgraph, where

K_{4} (t)

is obtained from a

K_{4}

by subdividing edges exactly

t - 4

times. The paper shows that every

K_{4} (t)

-minor free graph with maximum degree

Δ (G)

has

χ_{s}^{'} (G) \leq (t - 1) Δ (G)

for

t \in {5, 6, 7}

which generalizes some known results on

K_{4}

-minor free graphs by Batenburg, Joannis de Verclos, Kang, Pirot in 2022 and Wang, Wang, and Wang in 2018. These upper bounds are sharp. Full article

(This article belongs to the Special Issue Advances in Graph Theory and Combinatorial Optimization)

► Show Figures

Figure 1

11 pages, 680 KiB

Open AccessArticle

On 3-Restricted Edge Connectivity of Replacement Product Graphs

by Yilan Cui, Jianping Ou and Saihua Liu

Axioms 2023, 12(5), 504; https://0-doi-org.brum.beds.ac.uk/10.3390/axioms12050504 - 22 May 2023

Cited by 1 | Viewed by 881

Abstract

A 3-restricted edge cut is an edge cut of a connected graph that separates this graph into components, each having an order of at least 3. The minimum size of all 3-restricted edge cuts of a graph is called its 3-restricted edge connectivity. This work determines the upper and lower bounds on the 3-restricted edge connectivity of replacement product graphs and presents sufficient conditions for replacement product graphs to be maximally 3-restricted edge connected. As a result, the 3-restricted edge connectivity of replacement product graphs of some special graphs are determined. Full article

(This article belongs to the Special Issue Advances in Graph Theory and Combinatorial Optimization)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Advances in Graph Theory and Combinatorial Optimization

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Published Papers (7 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI