Search

Nikiforov defined the A α -matrix of a graph G as A α (G) = α D (G) + (1 − α) A (G) , where α ∈ [ 0 , 1 ] , D (G) and A (G) are the diagonal matrix of degrees and the adjacency matrix respectively. The largest eigenvalue of A α (G) is called the A α -spectral radius of G , denoted by ρ α (G). In this paper, we first give an upper bound on ρ α (G) of a connected graph G with fixed size m ≥ 3 k and maximum degree Δ ≤ m − k , where k is a positive integer. For two connected graphs G 1 and G 2 with size m ≥ 4 , employing this upper bound, we prove that ρ α (G 1) > ρ α (G 2) if Δ (G 1) > Δ (G 2) and Δ (G 1) ≥ 2 m 3 + 1. As an application, we determine the graph with the maximal A α -spectral radius among all graphs with fixed size and girth. Our theorems generalize the recent results for the signless Laplacian spectral radius of a graph. [ABSTRACT FROM AUTHOR]

Identifying the graph with maximum or minimum spectral radius among a given class of graphs is a central problem in extremal spectral graph theory, known as the Brualdi–Solheid problem. For a graph G = (V G , E G) , a subset S ⊆ V G is called a maximum dissociation set if the induced subgraph G [ S ] does not contain P 3 as its subgraph, and the subset has maximum cardinality. The dissociation number of G is the number of vertices in a maximum dissociation set of G. In this paper, we first characterize all the connected graphs (resp. bipartite graphs, trees) having maximum spectral radius among connected graphs (resp. bipartite graphs, trees) with given order and dissociation number. Secondly, we show that the connected n -vertex graph with dissociation number φ having minimum spectral radius is a tree, where φ ≥ 2 3 n. Finally, we determine the graphs having minimum spectral radius with fixed order n and dissociation number φ ∈ { 2 , ⌈ 2 n / 3 ⌉ , n − 1 , n − 2 }. [ABSTRACT FROM AUTHOR]

The degree diameter problem is a fundamental and well-studied problem in extremal graph theory, which deals with trade-offs among three parameters: the maximum degree, the diameter, and the number of vertices in a graph. In this paper, we introduce another parameter that represents the robustness of a network and investigate trade-offs among the parameters. For positive integers r and k , we say that a graph is (r , k) -connected if it contains r internally vertex-disjoint paths of length at most k between any pair of vertices. We consider an (r , k) -connected graph with n vertices whose maximum degree is minimized. Our contribution is to show that the minimum of the maximum degree of such a graph is Θ (max { r n k , r }) , which is a tight bound up to constant factors. [ABSTRACT FROM AUTHOR]

An interval graph is the intersection graph of a family F of intervals on the real line. An interval order is a partial order (F , ≺) , where F is a family of intervals on the real line, such that for all I 1 , I 2 ∈ F , I 1 ≺ I 2 if and only if I 1 lies entirely to the left of I 2. In both cases, the family F is called a model of the graph (order). The interval count of a given graph (resp. order) is the smallest number of interval lengths needed in any model of this graph (resp. order). The first problem we consider is related to the classes of graphs and orders which can be represented with two interval lengths a and b , with respect to the inclusion hierarchy among such classes for variables a , b. The second problem is an extremal problem which consists of determining the smallest graph or order which has interval count at least k. In particular, we study a conjecture by Fishburn on this extremal problem, verifying its validity when such a conjecture is constrained to the classes of trivially perfect orders and split orders. [ABSTRACT FROM AUTHOR]

A graph is minimally k -(edge)-connected if it is k -connected (respectively, k -edge-connected) and deleting any arbitrary chosen edge always leaves a graph which is not k -connected (respectively, k -edge-connected). What is the maximum (signless Laplacian) spectral radius and what are the corresponding extremal graphs among minimally k -(edge)-connected graphs for k ≥ 2 ? Chen and Guo (2019) gave the answer to k = 2 and characterized the corresponding extremal graphs. In this paper, we first give the answer to k = 3 for minimally 3-connected graphs. For the signless Laplacian spectral radius, we also consider the problem for k = 2 , 3 and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

The total number of independent subsets, including the empty set, of a graph, is also termed as the Merrifield–Simmons index (MSI) in mathematical chemistry. The connective eccentricity index (CEI), the multiplicative Wiener index (MWI), and the Wiener polarity index (WPI) are all distance-based topological indices. Some of these topological indices found applications in chemistry. The eccentric complexity of a graph G is defined to be the number of different eccentricities of its vertices. In this paper, we first investigate the relationship between MSI and three other distance-based topological indices (CEI, MWI, WPI). We prove that MSI > WPI for any tree, MSI > CEI for any connected bipartite graph, and MWI > MSI for connected graphs with given restricted condition on size. Then we consider extremal problems of MSI on graphs with small eccentric complexity. Moreover, we prove an inequality relating MSI, independence number and eccentric complexity for some special graph families. Finally, some further problems and conjectures are proposed. [ABSTRACT FROM AUTHOR]

In this paper, the extremal problems on the phenylene chains with respect to some graph invariants are studied. All the graphs minimizing (resp. maximizing) the coefficients sum of the permanental polynomial, the spectral radius, the Hosoya index and the Merrifield–Simmons index among all the phenylene chains each of which contains n four-membered rings are identified. [ABSTRACT FROM AUTHOR]

Abstract It is known that a positive Boolean function f depending on n variables has at least n + 1 extremal points, i.e. minimal ones and maximal zeros. We show that f has exactly n + 1 extremal points if and only if it is linear read-once. The class of linear read-once functions is known to be the intersection of the classes of read-once and threshold functions. Generalizing this result we show that the class of linear read-once functions is the intersection of read-once and Chow functions. We also find the set of minimal read-once functions which are not linear read-once and the set of minimal threshold functions which are not linear read-once. In other words, we characterize the class of linear read-once functions by means of minimal forbidden subfunctions within the universe of read-once and the universe of threshold functions. Within the universe of threshold functions the importance of linear read-once functions is due to the fact that they attain the minimum value of the specification number, which is n + 1 for functions depending on n variables. In 1995 Anthony et al. conjectured that for all other threshold functions the specification number is strictly greater than n + 1. We disprove this conjecture by exhibiting a threshold non-linear read-once function depending on n variables whose specification number is n + 1. [ABSTRACT FROM AUTHOR]

A connected graph is said to be a cactus if each of its blocks is either a cycle or an edge. Let C n be the set of all n -vertex cacti with circumference at least 4, and let C n , k be the set of all n -vertex cacti containing exactly k ⩾ 1 cycles where n ⩾ 3 k + 1 . In this paper, lower bounds on the difference between the (revised) Szeged index and Wiener index of graphs in C n (resp. C n , k ) are proved. The minimum and the second minimum values on the difference between the Szeged index and Wiener index of graphs among C n are determined. The bound on the minimum value is strengthened in the bipartite case. A lower bound on the difference between the revised Szeged index and Wiener index of graphs among C n , k is also established. Along the way the corresponding extremal graphs are identified. [ABSTRACT FROM AUTHOR]

The generalized A B C index of a graph G , denoted by A B C α ( G ) , is defined as the sum of weights ( d i + d j − 2 d i d j ) α over all edges v i v j of G , where α is an arbitrary non-zero real number, and d i is the degree of vertex v i of G . In this paper, we first prove that the generalized A B C index of a connected graph will increase with addition of edge(s) if α < 0 or 0 < α ≤ 1 ∕ 2 , which provides a useful tool for the study of extremal properties of the generalized A B C index. By means of this result, we then characterize the graphs having the maximal A B C α value for α < 0 among all connected graphs with given order and vertex connectivity, edge connectivity, or matching number. Our work extends some previously known results. [ABSTRACT FROM AUTHOR]

The Wiener index W ( G ) of a connected graph G is the sum of distances between all pairs of vertices of G . A connected graph G is said to be a cactus if each of its blocks is either a cycle or an edge. Let G n , t be the set of all n -vertex cacti containing exactly t cycles. Liu and Lu (2007) determined the unique graph in G n , t with the minimum Wiener index. We now establish a sharp upper bound on the Wiener index of graphs in G n , t and identify the corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

A segment of a tree T is a path whose end vertices have degree 1 or at least 3, while all internal vertices have degree 2. The lengths of all the segments of T form its segment sequence, in analogy to the degree sequence. We address a number of extremal problems for the class of all trees with a given segment sequence. In particular, we determine the extremal trees for the number of subtrees, the number of matchings and independent sets, the graph energy, and spectral moments. [ABSTRACT FROM AUTHOR]

The atom-bond connectivity ( A B C ) index of a graph G is defined as the sum of the weights d ( u ) + d ( v ) − 2 d ( u ) d ( v ) of all edges u v of G , where d ( u ) denotes the degree of a vertex u in G . In this short note, we determine the maximum A B C index for graphs with edge-connectivity one and characterize the corresponding extremal graphs. This answers a recent question proposed by Zhang et al. (2016). [ABSTRACT FROM AUTHOR]

We show that every C 6 -free graph G has a C 4 -free, bipartite subgraph with at least 3 e ( G ) / 8 edges. Our proof is probabilistic and uses a theorem of Füredi et al. (2006) on C 6 -free graphs. [ABSTRACT FROM AUTHOR]

A game starts with the empty graph on n vertices, and two players alternate adding edges to the graph. Only moves which do not create a triangle are valid. The game ends when a maximal triangle-free graph is reached. The goal of one player is to end the game as soon as possible, while the other player is trying to prolong the game. With optimal play, the length of the game (number of edges played) is called the K 3 game saturation number. In this paper we prove an upper bound for this number. [ABSTRACT FROM AUTHOR]

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Füredi conjectured that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -graphs with edges. Talbot in Talbot (2002) provided some evidences for Frankl and Füredi’s conjecture. In this paper, we prove that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -uniform graphs on vertices with edges when where under some conditions. As an implication, we also derive that Frankl and Füredi’s conjecture holds for 3-uniform graphs with edges where . [ABSTRACT FROM AUTHOR]

Abstract: Two players, Dominator and Staller, alternately choose vertices of a graph , one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of Dominator is to finish the game as soon as possible, while the aim of Staller is just the opposite. The game domination number is the number of vertices chosen when Dominator starts the game and both players play optimally. It has been conjectured in Kinnersley et al. (2012) [7] that holds for an arbitrary graph with no isolated vertices, which is in particular open when is a forest. In this paper, we present constructions that lead to large families of trees that attain the conjectured -bound. Some of these families can be used to construct graphs with game domination number of their order by gluing them to an arbitrary graph. All extremal trees on up to 20 vertices were found by a computer. In particular, there are exactly ten trees on 20 vertices with , all of which belong to the constructed families. [Copyright &y& Elsevier]

Abstract: A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. The complete graph on four vertices minus one edge is called a diamond, and a diamond-free graph has no induced diamond subgraph. In this paper we use an association with total domination to characterize the diameter-2-critical graphs whose complements are diamond-free. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order is at most and that the extremal graphs are the complete bipartite graphs . As a consequence of our characterization, we prove the Murty–Simon conjecture for graphs whose complements are diamond-free. [Copyright &y& Elsevier]

Abstract: A connected graph is total domination stable upon edge removal, if the removal of an arbitrary edge does not change the total domination number. We determine the minimum number of edges required for a total domination stable graph in terms of its order and total domination number. [Copyright &y& Elsevier]

Abstract: The Merrifield–Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by the set of connected graphs with vertices and cut vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield–Simmons index, respectively, among all graphs in for all possible values. [Copyright &y& Elsevier]

Abstract: The atom-bond connectivity (ABC) index of a graph is defined as where is the edge set and is the degree of vertex of . We give the best upper bound for the ABC index of trees with a perfect matching, and characterize the unique extremal tree, which is a molecular tree. We also give upper bounds for the ABC index of trees with fixed number of vertices and maximum degree, and of molecular trees with fixed numbers of vertices and pendent vertices, and characterize the extremal trees. [Copyright &y& Elsevier]

Abstract: A set of vertices of a connected graph is a doubly connected dominating set if every vertex not in is adjacent to some vertex in and the subgraphs induced by and are connected. The doubly connected domination number is the minimum size of such a set. We prove that when and are both connected of order , and we describe the two infinite families of extremal graphs achieving the bound. [Copyright &y& Elsevier]

Abstract: A polyhedron is integral if all its extreme points have 0, 1 components and in this case the matrix is called ideal. When has fractional extreme points, there are different ways of classifying how far is away from being ideal, through the polyhedral structure of . In this sense, Argiroffo, Bianchi and Nasini (2006)  defined a nonidealness index analogous to an imperfection index due to Gerke and McDiarmid (2001) . In this work we determine the nonidealness index of rank-ideal matrices (introduced by the authors (2008)). It is known that evaluating this index is -hard for any matrix. We provide a tractable way of evaluating it for most circulant matrices, whose blockers are a particular class of rank-ideal matrices, thereby following similar lines as done for the imperfection ratio of webs due to Coulonges, Pêcher and Wagler (2009) . Finally, exploiting the properties of this nonidealness index, we identify the facets of the set covering polyhedron of circulant matrices, having maximum strength with respect to the linear relaxation, according to a measure defined by Goemans (1995) . [Copyright &y& Elsevier]

Abstract: A semi-star tree is a star tree whose some edges may be replaced by paths of length more than one. In this paper we present some increasing and decreasing transformations for Szeged index of the semi-star trees. Then we introduce palm semi-star tree and uniform semi-star tree and show that they are extremal with respect to the Szeged index and edge Szeged index. In addition, we investigate the relation between the Szeged index and edge Szeged index for all trees. [Copyright &y& Elsevier]

Abstract: A fullerene graph is a cubic 3-connected plane graph with (exactly 12) pentagonal faces and hexagonal faces. Let be a fullerene graph with vertices. A set of mutually disjoint hexagons of is a sextet pattern if has a perfect matching which alternates on and off every hexagon in . The maximum cardinality of sextet patterns of is the Clar number of . It was shown that the Clar number is no more than . Many fullerenes with experimental evidence attain the upper bound, for instance, and . In this paper, we characterize extremal fullerene graphs whose Clar numbers equal . By the characterization, we show that there are precisely 18 fullerene graphs with 60 vertices, including , achieving the maximum Clar number 8 and we construct all these extremal fullerene graphs. [Copyright &y& Elsevier]

Abstract: Let be a connected plane graph, be the corresponding link diagram via medial construction, and be the number of components of the link diagram . In this paper, we first provide an elementary proof that , where is the nullity of . Then we lay emphasis on the extremal graphs, i.e. the graphs with . An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs. [Copyright &y& Elsevier]

Abstract: Let be a graph and denote the degree of a vertex in . The zeroth-order general Randić index of the graph is defined as , where the summation goes over all vertices of and is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected -graphs with minimum and maximum zeroth-order general Randić index, Discrete Appl. Math. 155 (8) (2007) 1044–1054] and give a more general Theorem. We finally characterize 1 [1] Note added in proof: We have learned in the meantime that correction of the main error and proof for have been obtained in ”- Graphs with maximum zeroth-order general Randić index for ” by X. Li, Y. Shi, MATCH, 62 (1) (2009). for the connected -graphs with maximum value , where is a simple connected graph with vertices and edges. [Copyright &y& Elsevier]

Abstract: By the extremal number we denote the maximum number of edges in a graph of order and girth at least . The set of such graphs is denoted by . In 1975, Erdős mentioned the problem of determining extremal numbers in a graph of order and girth at least five. In this paper, we consider a generalized version of the problem for any value of girth by using the hybrid simulated annealing and genetic algorithm (HSAGA). Using this algorithm, some new results for have been obtained. In particular, we generate some graphs of girth and 8 which in some cases have more edges than corresponding cages. Furthermore, future work will be described regarding the investigation of structural properties of such extremal graphs and the implementation of HSAGA using parallel computing. [Copyright &y& Elsevier]

Abstract: In this note, it is shown that every graph with no -minor is -list-colorable. We also give an extremal function for the existence for a -minor. Our proof implies that there is a linear time algorithm for showing that either has a -minor or is -choosable. In fact, if the latter holds, then the algorithm gives rise to a -list-coloring. [Copyright &y& Elsevier]

Given an even cyclic (+1,−1) sequence s=(s0,…,s2n−1) which consists of n plus ones and n minus ones, let us compute i+j (mod 2n) for all n2 (+1,−1)-pairs (si,sj) and insert the obtained n2 numbers into 2n “boxes” b0,b1,…,b2n−1, where box bk contains the multiplicity of k. The cyclic sequence B(s)=(b0,b1,…,b2n−1) is referred to as the box distribution of s. The average cardinality of a box is n2/2n=n/2. Some sequences have quite remarkable box-distributions, “almost average everywhere with two big humps”. For example, n=5, s=(+1+1−1−1+1−1+1−1−1+1), B=(3333133330)=(341 340); n=7, s=(+1+1+1−1+1−1−1−1+1+1−1+1−1−1), B=(33333363333337)=(366 367). In general, given an odd n, the box-distributions (⌊n/2⌋n−1(n−1)⌊n/2⌋n−1n) and (⌈n/2⌉n−11⌈n/2⌉n−10) as well as the sequences which generate them, will be called the camel distributions and camel sequences, respectively, up-camel and down-camel. For example, the first sequence above is down-camel, and the second one is up-camel. Here we prove that there are infinitely many ‘camels’ of both types. More precisely, for every prime n=4j−1 we construct an up-camel sequence and for every prime n=4j+1 a down-camel one. In both cases these sequences are related to quadratic residues and non-residues modulo n. Camel sequences have applications in extremal graph theory. [Copyright &y& Elsevier]

Consider a matrix satisfying the following two properties. There are no two rows of the matrix having the same entries in two cyclically neighbouring columns. On the other hand for each subset of the columns not containing a cyclically neighbouring pair there are two rows having the same entries in these columns. In this paper the magnitude of the minimal number of the rows of such a matrix will be determined for given number of columns. Using the same method, the analogue question can be answered for some other Sperner-systems, too. The heart of the proof is a combinatorial lemma, which might be interesting in itself. [Copyright &y& Elsevier]

Given a monotone property P of graphs, write Pn for the set of graphs with vertex set [n] having property P. Building on recent results in the enumeration of graphical properties, we prove numerous results about the structure of graphs in Pn and the functions |Pn|. We also examine the measure eP(n), the maximum number of edges in a graph of Pn. [Copyright &y& Elsevier]

In Vukićević and Stevanović (2013), Theorem 2 is erroneous when m = 3 k + 1 for some integer k . The correct one is given now. That is, P I ( G ) ≥ m 2 − 3 m + 2 when m = 3 k + 1 for some integer k , where G is a connected bicyclic graph with m edges. [ABSTRACT FROM AUTHOR]