Search

The normalized algebraic connectivity of a graph with order n , denoted by ρ n − 1 , is the second smallest eigenvalue of the normalized Laplacian matrix of the graph. In this paper, we determine the graphs with ρ n − 1 ≥ 3 n − 8 3 n − 9 by using forbidden subgraph characterization. A stronger result on bipartite graph is also obtained. [ABSTRACT FROM AUTHOR]

We consider a variation of the Cops and Robbers game in which the cops do not have perfect information; the information they receive regarding the robber's position is delayed by one round. Our parameter of interest is the time-delayed cop number of a graph G , the minimum number of cops that suffice to guarantee a win on G. We present a variety of results on this parameter, including general bounds, and make comparisons to the cop numbers of known related variants of the original game. We have particular interest in graph products, Meyniel-type bounds, and cop density. [ABSTRACT FROM AUTHOR]

A graph G has the strong parity property if for every subset X ⊆ V (G) with | X | even, G has a spanning subgraph F satisfying δ (F) ≥ 1 , d F (u) ≡ 1 (mod 2) for any u ∈ X , and d F (v) ≡ 0 (mod 2) for any v ∈ V (G) ∖ X. In this paper, we give a spectral radius condition to guarantee that a connected graph has the strong parity property. [ABSTRACT FROM AUTHOR]

An { A , B , C , ... } -factor of a graph G is defined to be a spanning subgraph of G such that each component of which is isomorphic to one of { A , B , C , ... }. Let A α (G) = α D (G) + (1 − α) A (G) , where D (G) denotes the diagonal matrix of vertex degrees of G and A (G) denotes the adjacency matrix of G. The largest eigenvalue of A α (G) is called the A α -spectral radius of G. In this paper, we explore the connections between the eigenvalues and the existence of a { K 2 , C 2 i + 1 : i ≥ 1 } -factor in a graph. We derive a tight sufficient condition involving the A α -spectral radius to ensure the existence of a { K 2 , C 2 i + 1 : i ≥ 1 } -factor in a graph, which generalizes the result on α = 0 obtained by Chen, Lv and Li [8]. Moreover, we present a tight distance signless Laplacian spectral radius condition for the existence of a { K 2 , C 2 i + 1 : i ≥ 1 } -factor in a graph. [ABSTRACT FROM AUTHOR]

A spanning k -tree of a connected graph G is a spanning tree in which each vertex admits degree at most k. It is easy to see that a spanning 2-tree is a Hamiltonian path. Hence, a spanning k -tree is an extended concept of a Hamiltonian path. Let Q (G) denote the distance signless Laplacian matrix of a graph G. The largest eigenvalue η 1 (G) of Q (G) is called the distance signless Laplacian spectral radius of G. Liu and Li characterized a connected graph with a perfect matching with respect to the distance signless Laplacian spectral radius (Liu and Li, 2021). Win characterized a connected graph with a spanning k -tree via the number of connected components (Win, 1989). Motivated by Liu and Li's and Win's results, in this paper we investigate the relations between the spanning k -tree and the distance signless Laplacian spectral radius in a connected graph and prove an upper bound for η 1 (G) in a connected graph G to guarantee the existence of a spanning k -tree. [ABSTRACT FROM AUTHOR]

A mobile agent, which is an autonomous device navigating in a graph, has to explore a given graph by visiting all of its nodes. We adopt the (arguably) weakest possible model of such a device: a deterministic memoryless automaton (DMA), i.e., a deterministic automaton with a single state. As expected, such a weak machine is incapable of exploring many graphs without marking nodes. Hence we allow the agent to use identical movable pebbles that can be dropped on nodes or picked from them. It turns out that this marking capability significantly enhances the exploration power of the agent. Our goal is to study how the availability of pebbles impacts the class of graphs that a DMA can explore. We first concentrate on finite graphs and show that any finite tree can be explored by a DMA without pebbles but there exist (small) finite graphs that cannot be explored by a DMA without pebbles. Then we turn attention to infinite graphs and fully characterize the class of infinite trees that can be explored by a DMA without pebbles. We also define a large class of infinite trees that can be explored by a DMA with finitely many pebbles. It turns out that many of these trees cannot be explored by a DMA without pebbles. On the other hand, we show a large class of infinite trees that cannot be explored by a DMA with finitely many pebbles. Thus, availability of pebbles yields a strict hierarchy of difficulty of exploration of infinite graphs by a DMA, and this hierarchy is strict even for the class of infinite trees: some trees can be explored without pebbles, some trees can be explored with finitely many pebbles but not without pebbles, and some trees require infinitely many pebbles. Finally, we consider exploration by a DMA with infinitely many pebbles. It turns out that all infinite trees can be explored by a DMA with infinitely many pebbles. By contrast, we construct infinite graphs that cannot be explored by any DMA, even with infinitely many pebbles. [ABSTRACT FROM AUTHOR]

An isolating set in a graph is a set X of vertices such that every edge of the graph is incident with a vertex of X or its neighborhood. The isolation number of a graph, or equivalently the vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least 6. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound. [ABSTRACT FROM AUTHOR]

The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χ o (F) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F. For the family of hexagonal grids H 2 , Bielak (2006) proved that 5 ≤ χ o (H 2) ≤ 6. Here we close the gap by showing that χ o (H 2) ≥ 6. [ABSTRACT FROM AUTHOR]

Assume there exists a function h : E (G) → [ 0 , 1 ] such that g (x) ≤ ∑ e ∈ E (G) , x ∋ e h (e) ≤ f (x) for every vertex x of G. The spanning subgraph of G induced by the set of edges { e ∈ E (G) : h (e) > 0 } is called a fractional (g , f) -factor of G with indicator function h. Let M and N be two disjoint sets of independent edges of G satisfying | M | = m and | N | = n. We say that G possesses a fractional (g , f) -factor with the property E (m , n) if G contains a fractional (g , f) -factor with indicator function h such that h (e) = 1 for each e ∈ M and h (e) = 0 for each e ∈ N. In this article, we discuss stability number and minimum degree conditions for graphs to possess fractional (g , f) -factors with the property E (1 , n). Furthermore, we explain that the stability number and minimum degree conditions declared in the main result are sharp. [ABSTRACT FROM AUTHOR]

For non-decreasing sequence of integers (a 1 , a 2 , ... , a k) , an (a 1 , a 2 , ... , a k) -packing coloring of G is a partition of V (G) into k subsets V 1 , V 2 , ... , V k such that the distance between any two vertices x , y ∈ V i is at least a i + 1 , 1 ≤ i ≤ k. Yang and Wu (2023) proved that every 3-irregular subcubic graph is (1 , 1 , 3) -packing colorable. We introduce here a simpler and shorter proof of this result. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a finite, combinatorial graph. We define a notion of curvature on the vertex set V via the inverse of the resistance distance matrix. We prove that this notion of curvature has a number of desirable properties. Graphs with curvature bounded from below by K > 0 have diameter bounded from above. The Laplacian L = D − A satisfies a Lichnerowicz estimate, there is a spectral gap λ 2 ≥ 2 K. We obtain matching two-sided bounds on the maximal commute time between any two vertices in terms of | E | ⋅ | V | − 1 ⋅ K − 1 . Moreover, we derive quantitative rates for the mixing time of the corresponding Markov chain and prove a general equilibrium result. [ABSTRACT FROM AUTHOR]

The toughness of a graph G is defined to be the minimum value of | S | / k (G − S) , where k (G − S) denotes the number of components of G − S and the minimum is taken over all cut-sets S ⊆ V (G). In this paper we propose a version for weighted graphs that depends on the weights in both S and G − S. Apart from considering bounds and basic properties, our focus is on the problem of assigning weights so as to maximize the parameter. [ABSTRACT FROM AUTHOR]

Let G be a (simple) graph on n ≥ 3 vertices and (d 1 , ... , d n) be the degree sequence of G with d 1 ≤ ⋯ ≤ d n . The classical Chvátal's theorem states that if d m ≥ m + 1 or d n − m ≥ n − m for each m with 1 ≤ m < n 2 (called the Chvátal-condition), then G is hamiltonian. Similarly, let G be a (simple) balanced bipartite graph on n ≥ 4 vertices and (d 1 , ... , d n) be the degree sequence of G with d 1 ≤ ⋯ ≤ d n . The classical Chvátal's theorem states that if d m ≥ m + 1 or d n 2 ≥ n 2 − m + 1 for each m with 1 ≤ m ≤ n 4 (called the Chvátal-condition), then G is hamiltonian. In this paper, for an abelian group A of order at least 4, we show that if a graph G satisfies the Chvátal-condition, then G is A -connected if and only if G ≠ C 4 , where C ℓ is a cycle of length ℓ. Moreover, for an abelian group A of order at least 5, we also show that if a balanced bipartite graph G satisfies the Chvátal-condition, then G is A -connected if and only if G ≠ C 6 . [ABSTRACT FROM AUTHOR]

An integer k -matching of a graph G is a function h : E (G) → { 0 , 1 , ... , k } such that ∑ e ∈ Γ (v) h (e) ≤ k for any v ∈ V (G) , where Γ (v) is the set of edges incident to v. The integer k -matching number of G , denoted by m k (G) , is the maximum number of ∑ e ∈ E (G) h (e) over all integer k -matching h of G. In this paper, we establish the following lower bounds on the sum of the integer k -matching number of a graph G and its complement by using Gallai–Edmonds Structure Theorem: (1) m k (G) + m k (G ¯) ≥ ⌊ n k 2 ⌋ for n ≥ 2 ; (2) if G and G ¯ are non-empty, then for n ≥ 25 , m k (G) + m k (G ¯) ≥ ⌊ n k + k 2 ⌋ ; (3) if G and G ¯ have no isolated vertices, then for n ≥ 25 , m k (G) + m k (G ¯) ≥ ⌊ n k 2 ⌋ + 2 k. Furthermore, all extremal graphs attaining the lower bounds are also characterized. [ABSTRACT FROM AUTHOR]

We define, for any graph G = (V , E) , a boundary ∂ G ⊆ V. The definition coincides with what one would expected for the discretization of (sufficiently nice) Euclidean domains and contains all vertices from the Chartrand, Erwin, Johns & Zhang boundary. Moreover, it satisfies an isoperimetric principle stating that graphs with many vertices have a large boundary unless they contain long paths: we show that for graphs with maximaldegree Δ | ∂ G | ≥ 1 2 Δ | V | diam (G) . For graphs discretizing Euclidean domains, one has diam (G) ∼ | V | 1 / d and recovers the scaling of the classical Euclidean isoperimetric principle. [ABSTRACT FROM AUTHOR]

In 1975, P. Erdős proposed the problem of determining the maximum number f (n) of edges in a graph on n vertices in which any two cycles are of different lengths. Let f ∗ (n) be the maximum number of edges in a simple graph on n vertices in which any two cycles are of different lengths. Let M n be the set of simple graphs on n vertices and f ∗ (n) edges in which any two cycles are of different lengths. Let m c (n) be the maximum cycle length for all G ∈ M n . In this paper, it is proved that for n sufficiently large, m c (n) ≤ 15 16 n. We make the following conjecture: Conjecture. lim n → ∞ m c (n) n = 0. [ABSTRACT FROM AUTHOR]

In 2012 we announced "the House of Graphs" (https://houseofgraphs.org) (Brinkmann et al. 2013), which was a new database of graphs. The House of Graphs hosts complete lists of graphs of various graph classes, but its main feature is a searchable database of so called "interesting" graphs, which includes graphs that already occurred as extremal graphs or as counterexamples to conjectures. An important aspect of this database is that it can be extended by users of the website. Over the years, several new features and graph invariants were added to the House of Graphs and users uploaded many interesting graphs to the website. But as the development of the original House of Graphs website started in 2010, the underlying frameworks and technologies of the website became outdated. This is why we completely rebuilt the House of Graphs using modern frameworks to build a maintainable and expandable web application that is future-proof. On top of this, several new functionalities were added to improve the application and the user experience. This article describes the changes and new features of the new House of Graphs website. [ABSTRACT FROM AUTHOR]

A graph G is said to be fractional (a , b , k) -critical covered if for any W ⊆ V (G) with | W | = k , G − W is fractional [ a , b ] -covered. In this article, we demonstrate that a graph G of order n is fractional (a , b , k) -critical covered if G satisfies δ (G) ≥ (t − 1) (a + 1) + k , n ≥ (a + b) (t (a + b) − 2) + b k + 2 b , and | N G (x 1) ∪ N G (x 2) ∪ ⋯ ∪ N G (x t) | ≥ a n + b k + 2 a + b for any independent subset { x 1 , x 2 , ... , x t } of G , which is an improvement and extension of Yuan and Hao's previous result (Yuan and Hao, 2020). [ABSTRACT FROM AUTHOR]

Isolated toughness of graph G is formulated by minimizing the ratio | S | / i (G − S) over all S ⊆ V (G) with i (G − S) ≥ 2 , where i (G − S) is the number of isolated vertices after removing vertex subset S from G. The previous works reveal that there exist explicit correlations between isolated toughness and fractional critical graphs (a.k.a. the graph admits a fractional factor after deleting given number of vertices). However, among the existing isolated toughness bounds, the term with respect to n (the number of removed vertices) is always at least n. In this paper, the exactly sharp isolated toughness bound for fractional (k , n) -critical graph is determined which reveals that the coefficient of term with regard to n can be reduced to 1/2. It is well acknowledged that some tight toughness related bounds can reach to the extreme value, while others cannot. We give an explanation why these tight bounds in various settings possess such pattern differences. [ABSTRACT FROM AUTHOR]

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

The linear arboricity l a (G) of a graph G is the minimum number of linear forests which partition the edges of G. In 1980, Akiyama et al. conjectured that for any graph G , ⌈ Δ (G) 2 ⌉ ≤ l a (G) ≤ ⌈ Δ (G) + 1 2 ⌉. In the paper, we establish two essential structural properties of K 5 -minor free graphs G , one is used to confirm the conjecture for all K 5 -minor free graphs, the other is devoted to proving that l a (G) = ⌈ Δ (G) 2 ⌉ holds if Δ (G) ≥ 9. In addition, we prove here that if G is a K 5 − -minor free graph and Δ (G) ≥ 5 , then l a (G) = ⌈ Δ (G) 2 ⌉. [ABSTRACT FROM AUTHOR]

Let G be a graph and T a spanning tree of G. For an edge e in G − T , there is a cycle in T ∪ { e }. We call those edges cycle-edges and those cycles tree-cycles. The intersection of two tree-cycles is the set of all edges in common. If the intersection of two distinct tree-cycles is not empty, we regard that as an intersection. The tree intersection number of T is the number of intersections among all tree-cycles of T. In this paper, we prove the conjecture, posed by Dubinsky et al. (2021), which states that if a graph admits a star spanning tree in which one vertex is adjacent to all other vertices, then the star spanning tree has the minimum tree intersection number. [ABSTRACT FROM AUTHOR]

We define a graph G as well-hued if for each positive integer k there is an integer a k such that every maximal k -colorable subgraph of G has order a k. This strengthens the notion of well-covered graphs. In this paper we investigate the connection between this property and related properties, characterize the sequences of the a k that can be achieved, and determine conditions for the property in some graph classes and under some graph operations such as products. [ABSTRACT FROM AUTHOR]

A graph G is P ≥ k -factor deleted if for every edge e ∈ E (G) , G contains a P ≥ k -factor that excludes e. We first define the concept of (P ≥ k , n) -critical deleted graph, that is, a graph G is (P ≥ k , n) -critical deleted if for every subset D ⊆ V (G) with | D | = n , the graph G − D is P ≥ k -factor deleted. Clearly, a (P ≥ k , 0) -critical deleted graph is a P ≥ k -factor deleted graph. In this paper, we verify that (i) an (n + 2) -connected graph G is (P ≥ 2 , n) -critical deleted if its binding number b i n d (G) > 3 + n 4 ; (ii) an (n + 2) -connected graph G is (P ≥ 3 , n) -critical deleted if its binding number b i n d (G) > 3 + n 2 . Furthermore, we claim that two results above are best possible in some sense. [ABSTRACT FROM AUTHOR]

In communication networks, the existence of fractional factors can be characterized as the feasibility of data transmission. When some nonadjacent nodes with each other are damaged and a special channel is assigned, the possibility of data transmission in a communication network is equivalent to the existence of fractional ID-factor-critical covered graph. As a consequence, the existence of fractional ID- [ a , b ] -factor-critical covered graph plays a key role in studying data transmissions of communication networks. Neighborhood and minimum degree of a graph or a network are often used to measure the vulnerability and robustness of a graph or a network, which are two important parameters considered in network design. In this article, we mainly investigate the relationship between neighborhood of independent set, minimum degree and the fractional ID- [ a , b ] -factor-critical covered graph, and acquire a neighborhood of independent set and minimum degree condition for a graph being fractional ID- [ a , b ] -factor-critical covered, which is a generalization of the previous results. [ABSTRACT FROM AUTHOR]

The node reliability of a graph G is the probability that at least one node is operational and that the operational nodes can all communicate in the subgraph that they induce, given that the edges are perfectly reliable but each node operates independently with probability p ∈ [ 0 , 1 ]. We show that unlike many other notions of graph reliability, the number of maximal intervals of decrease in [ 0 , 1 ] is unbounded, and that there can be arbitrarily many inflection points in the interval as well. [ABSTRACT FROM AUTHOR]

The secure domination numbers of the Cartesian products of two small graphs with paths or cycles is determined, as well as for Möbius ladder graphs. Prior to this work, in all cases where the secure domination number has been determined, the proof has either been trivial, or has been derived from lower bounds established by considering different forms of domination. However, the latter mode of proof is not applicable for most graphs, including those considered here. Hence, this work represents the first attempt to determine secure domination numbers via the properties of secure domination itself, and it is expected that these methods may be used to determine further results in the future. [ABSTRACT FROM AUTHOR]

The connectivity and diagnosability of a system or an interconnection network are two important measures. As a topology structure of interconnection networks, the godan graph E A n has many good properties. In this paper, we give various connectivity of E A n and two diagnosability of E A n under the comparison diagnosis model. [ABSTRACT FROM AUTHOR]

Let G be a graph and h : E (G) → [ 0 , 1 ] be a function. If g (x) ≤ ∑ e ∋ x h (e) ≤ f (x) for every x ∈ V (G) , then we call a graph F h with vertex set V (G) and edge set E h a fractional (g , f) -factor of G with indicator function h , where e ∋ x means the edge e incident to vertex x in G and E h = { e : e ∈ E (G) , h (e) > 0 }. We say that G admits property E (m , n) with respect to fractional (g , f) -factor if for any two sets of independent edges M and N with | M | = m , | N | = n and M ∩ N = 0̸ , G admits a fractional (g , f) -factor F h such that h (e) = 1 for any e ∈ M and h (e) = 0 for any e ∈ N. In this paper, we show a lower bound on binding number which guarantees a graph G to have property E (1 , n) with respect to fractional (g , f) -factor. [ABSTRACT FROM AUTHOR]

A tensegrity graph is a graph with edges labeled as bars, cables and struts. A realization of a tensegrity graph T is a pair (T , p) , where p maps the vertices of T into R d for some d ≥ 1. The realization is globally rigid if any realization (T , q) in R d in which the bars have the same length and the cables and struts are not longer and not shorter, respectively, is an isometric image of (T , p). A tensegrity graph is weakly globally rigid in R d if it has a generic globally rigid realization in R d , and strongly globally rigid in R d if every generic realization in R d is globally rigid. In this paper we give a necessary condition for weak global rigidity in R d and prove that in the d = 1 case the same condition is also sufficient. In particular, our results imply that a tensegrity graph has a generic globally rigid realization in R 1 if and only if it has a generic universally rigid realization in R 1. We also show that recognizing strongly globally rigid tensegrity graphs in R d is co-NP-hard for all d ≥ 1. [ABSTRACT FROM AUTHOR]

The line sum optimization problem asks for a (0 , 1) -matrix minimizing the sum of given functions evaluated at its row and column sums. We show that the uniform problem, with identical row functions and identical column functions, and the monotone problem, over matrices with nonincreasing row and column sums, are polynomial time solvable. [ABSTRACT FROM AUTHOR]

We consider the problem of finding a subgraph of a given graph minimizing the sum of given functions at vertices evaluated at their subgraph degrees. While the problem is NP-hard already for bipartite graphs when the functions are convex on one side and concave on the other, we have that when all functions are convex, the problem can be solved in polynomial time for any graph. We also provide polynomial time solutions for bipartite graphs with one side fixed for arbitrary functions, and for arbitrary graphs when all but a fixed number of functions are either nondecreasing or nonincreasing. We note that the general factor problem and the (l,u)-factor problem over a graph are special cases of our problem, as well as the intriguing exact matching problem. The complexity of the problem remains widely open, particularly for arbitrary functions over complete graphs. [ABSTRACT FROM AUTHOR]

Several topological indices (second Zagreb index, augmented Zagreb index, atom-bond connectivity index etc.) are possibly the graph-based molecular structure descriptors most widely applied in chemistry and pharmacology. One important aspect in the study of topological indices is their discrimination ability. In view of this, the exponential vertex-degree-based topological index was introduced in the literature. Cruz et al. (2020) mentioned some open problems on the exponential vertex-degree-based topological indices of trees. In this paper, we solve two open problems on the exponential second Zagreb index and the exponential augmented Zagreb index of trees. Moreover, we present some bounds on the exponential atom-bond connectivity index of graphs and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

The spectral radius ρ (G) of a graph G is the largest eigenvalue of its adjacency matrix A (G). In this paper, we first give a sharp lower bound of the spectral radius of a graph G in terms of the degree and the average 2-degree which generalizes a result of Das and Kumar (2003), and then as an application, a sharp upper bound of the energy of G is given which generalizes a result of Liu et al. (2007). [ABSTRACT FROM AUTHOR]

This paper presents a phenomenon which sometimes occurs in tetravalent bipartite locally dart-transitive graphs, called a Base Graph–Connection Graph dissection. In this dissection, each white vertex is split into two vertices of valence 2 so that the connected components of the result are isomorphic. Given the Base Graph whose subdivision is isomorphic to each component, and the Connection Graph, which describes how the components overlap, we can, in some cases, provide a construction which can make a graph having such a decomposition. This paper investigates the general phenomenon as well as the special cases in which the connection graph has no more than one edge. [ABSTRACT FROM AUTHOR]

The total number of independent subsets, including the empty set, of a graph, is also termed as the Merrifield–Simmons index (M S I) in mathematical chemistry. The eccentric complexity of a graph G is defined to be the number of different eccentricities of its vertices. Hua et al. (2020) mentioned two open problems and a conjecture on the Merrifield–Simmons index and eccentric complexity of graph. In this paper we solve both open problems and a conjecture. Moreover, we generalize some of the results. [ABSTRACT FROM AUTHOR]

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m (G). It was shown by Saks and Werman that m (K n) = n − b (n) , where b (n) is the number of 1's in the binary representation of n. In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph G on n vertices are n − b (n) ≤ m (G) ≤ n − 1. We show that for any tree T on an even number of vertices we have m (T) = n − 1 , and that for any tree T on an odd number of vertices, we have n − 65 ≤ m (T) ≤ n − 2. Our proof uses results about the weighted version of the problem for K n , which may be of independent interest. We also exhibit a sequence G n of graphs with m (G n) = n − b (n) such that G n has O (n b (n)) edges and n vertices. [ABSTRACT FROM AUTHOR]

Let m , n , r and k i (1 ≤ i ≤ m) be positive integers with n ≤ m and k 1 ≥ k 2 ≥ ⋯ ≥ k m ≥ 2 r − 1. Let G be a graph, and let H 1 , H 2 , ... , H r be vertex-disjoint n -subgraphs of G. It is verified in this article that every 0 , k 1 + k 2 + ⋯ + k m − n + 1 -graph G includes a subgraph R such that R has a 0 , k i 1 n -factorization orthogonal to every H i , 1 ≤ i ≤ r. [ABSTRACT FROM AUTHOR]

The connectivity is an important measurement for the fault-tolerance of networks. The structure connectivity and substructure connectivity are two generalizations of the classical connectivity. For a fixed graph H , a set F of subgraphs of G is called an H -structure cut (resp., H -substructure cut) of G , if G − ∪ F ∈ F V (F) is disconnected and every element of F is isomorphic to H (resp., a connected subgraph of H). The H -structure connectivity (resp., H -substructure connectivity) of G , denoted by κ (G ; H) (resp., κ s (G ; H)), is the cardinality of a minimal H -structure cut (resp., H -substructure cut) of G. In this paper, we will establish both κ (S n ; H) and κ s (S n , H) for every H ∈ { K 1 , K 1 , 1 , K 1 , 2 , ... , K 1 , n − 2 , P 4 , P 5 , C 6 } , where S n is the n -dimensional star graph. These results will show that star networks are highly tolerant of structure faults. [ABSTRACT FROM AUTHOR]

In a recent article by Bona and Vince, the authors studied the concept of an assembly tree for a graph motivated by the way that macromolecules assemble. Assembly trees act as record keeping devices for the construction of a given graph from its vertices. In the original article, graphs were to be assembled following an edge gluing rule for the vertices. In this paper, we first define and enumerate assembly trees that are constructed using a connected gluing rule. Following this, we examine how introducing a notion of time to assembly trees changes how they are counted using both gluing rules. [ABSTRACT FROM AUTHOR]

This paper is the first from a series of papers that establish a common analogue of the strong component and basilica decompositions for bidirected graphs. A bidirected graph is a graph in which a sign ＋ or − is assigned to each end of each edge, and therefore is a common generalization of digraphs and signed graphs. Unlike digraphs, the reachabilities between vertices by directed trails and paths are not equal in general bidirected graphs. In this paper, we set up an analogue of the strong connectivity theory for bidirected graphs regarding directed trails, motivated by degree-bounded factor theory. We define the new concepts of circular connectivity and circular components as generalizations of the strong connectivity and strong components. In our main theorem, we characterize the inner structure of each circular component; we define a certain binary relation between vertices in terms of the circular connectivity and prove that this relation is an equivalence relation. The nontrivial aspect of this structure arises from directed trails starting and ending with the same sign, and is therefore characteristic to bidirected graphs that are not digraphs. This structure can be considered as an analogue of the general Kotzig–Lovász decomposition, a known canonical decomposition in 1-factor theory. From our main theorem, we also obtain a new result in b -factor theory, namely, a b -factor analogue of the general Kotzig–Lovász decomposition. [ABSTRACT FROM AUTHOR]

In 1975, P. Erdős proposed the problem of determining the maximum number f (n) of edges in a graph with n vertices in which any two cycles are of different lengths. The sequence (c 1 , c 2 , ... , c n) is the cycle length distribution of a graph G with n vertices, where c i is the number of cycles of length i in G. Let f (a 1 , a 2 , ... , a n) denote the maximum possible number of edges in a graph which satisfies c i ≤ a i , where a i is a nonnegative integer. In 1991, Shi posed the problem of determining f (a 1 , a 2 , ... , a n) which extended the problem due to Erdős. It is clear that f (n) = f (1 , 1 , ... , 1). Let g (n , m) = f (a 1 , a 2 , ... , a n) , where a i = 1 if i ∕ m is an integer, and a i = 0 otherwise. It is clear that f (n) = g (n , 1). We prove that lim inf n → ∞ f (n) − n n ≥ 2 + 40 99 , which is better than the previous bounds 2 (Shi (1988)), and 2 + 7654 19071 (Lai (2017)). We show that lim inf n → ∞ g (n , m) − n n m > 2. 444 , for all even integers m. We make the following conjecture: lim inf n → ∞ f (n) − n n > 2. 444. [ABSTRACT FROM AUTHOR]

We compute the treewidth of a family of graphs we refer to as the glued grids, consisting of the stacked prism graphs and the toroidal grids. Our main technique is constructing strict brambles of large orders. We discuss connections to divisorial graph theory coming from tropical geometry, and use our results to compute the divisorial gonality of these graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with n (G) vertices and e (G) edges. The elementary cyclic number c (G) of G is defined as c (G) = e (G) − n (G) + ω (G) , where ω (G) is the number of connected components of G. The nullity of G , denoted by η (G) , is the multiplicity of the eigenvalue zero of the adjacency matrix of G. A graph is leaf-free if it has no pendent vertices. In Ma et al. (2016) proved that if G is leaf-free and each component of G contains at least two vertices, then η (G) ≤ 2 c (G) , the equality is attained if and only if G is the union of disjoint cycles, where each cycle has length a multiple of 4. In this paper, we completely characterize all leaf-free graphs with nullity one less than the above upper bound, i.e., η (G) = 2 c (G) − 1. [ABSTRACT FROM AUTHOR]