Extremal graph theory for metric dimension and diameter.
Extremal inverse eigenvalue problem for matrices described by a connected unicyclic graph
In this paper, we deal with the construction of symmetric matrix whose corresponding graph is connected and unicyclic using some pre-assigned spectral data. Spectral data for the problem consist of the smallest and the largest eigenvalues of each leading principal submatrices. Inverse eigenvalue problem (IEP) with this set of spectral data is generally known as the extremal IEP. We use a standard scheme of labeling the vertices of the graph, which helps in getting a simple relation between the characteristic...
Extremal Matching Energy of Complements of Trees
Gutman and Wagner proposed the concept of the matching energy which is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph. And they pointed out that the chemical applications of matching energy go back to the 1970s. Let T be a tree with n vertices. In this paper, we characterize the trees whose complements have the maximal, second-maximal and minimal matching energy. Furthermore, we determine the trees with edge-independence number p whose complements have...
Extremal problems for forbidden pairs that imply hamiltonicity
Let C denote the claw , N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does...
Extremal problems for -partite and -colorable hypergraphs.
Extremal Properties of the Chromatic Polynomials of Connected 3-chromatic Graphs
Extremal trees and molecular trees with respect to the Sombor-index-like graph invariants and
I. Gutman (2022) constructed six new graph invariants based on geometric parameters, and named them Sombor-index-like graph invariants, denoted by . Z. Tang, H. Deng (2022) and Z. Tang, Q. Li, H. Deng (2023) investigated the chemical applicability and extremal values of these Sombor-index-like graph invariants, and raised some open problems, see Z. Tang, Q. Li, H. Deng (2023). We consider the first open problem formulated at the end of Z. Tang, Q. Li, H. Deng (2023). We obtain the extremal values...
Extremal Unicyclic Graphs With Minimal Distance Spectral Radius
The distance spectral radius ρ(G) of a graph G is the largest eigenvalue of the distance matrix D(G). Let U (n,m) be the class of unicyclic graphs of order n with given matching number m (m ≠ 3). In this paper, we determine the extremal unicyclic graph which has minimal distance spectral radius in U (n,m) Cn.
Extreme distances in multicolored point sets.
Extreme geodesic graphs
For two vertices and of a graph , the closed interval consists of , , and all vertices lying in some geodesic of , while for , the set is the union of all sets for . A set of vertices of for which is a geodetic set for , and the minimum cardinality of a geodetic set is the geodetic number . A vertex in is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in is its extreme order . A graph is an extreme geodesic...
Extremely Irregular Graphs
Extremizing algebraic connectivity subject to graph theoretic constraints.
Extremum degree sets of irregular oriented graphs and pseudodigraphs
A digraph in which any two vertices have distinct degree pairs is called irregular. Sets of degree pairs for all irregular oriented graphs (also loopless digraphs and pseudodigraphs) with minimum and maximum size are determined. Moreover, a method of constructing corresponding irregular realizations of those sets is given.
-continuous graphs
For a nontrivial connected graph , the -degree of a vertex in a graph is the number of copies of in containing . A graph is -continuous (or -degree continuous) if the -degrees of every two adjacent vertices of differ by at most 1. All -continuous graphs are determined. It is observed that if is a nontrivial connected graph that is -continuous for all nontrivial connected graphs , then either is regular or is a path. In the case of a 2-connected graph , however, there...
-Geometric Mean Labeling of some Chain Graphs and Thorn graphs
Face size and the maximum genus of a graph. II: Nonsimple graphs
Facetas del politopo de recubrimiento con coeficientes en {0, 1, 2, 3}.
En dos artículos, publicados en 1989, Balas y Ng dan una metodología para construir facetas del politopo de recubrimiento con coeficientes en {0, 1, 2}. Siguiendo esta metodología, en el presente artículo decimos cómo se contruyen facetas de dicho politopo con coeficientes en {0, 1, 2, 3}.
Face-width of embedded graphs
Factor-criticality and matching extension in DCT-graphs
The class of DCT-graphs is a common generalization of the classes of almost claw-free and quasi claw-free graphs. We prove that every even (2p+1)-connected DCT-graph G is p-extendable, i.e., every set of p independent edges of G is contained in a perfect matching of G. This result is obtained as a corollary of a stronger result concerning factor-criticality of DCT-graphs.
Factoring directed graphs with respect to the cardinal product in polynomial time
By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.