Search

Let G be a graph and d i be the degree of a vertex v i in G. For a symmetric real function f (x , y) , one can get an edge-weighted graph in such a way that for each edge v i v j of G , the weight of v i v j is assigned by f (d i , d j). Hence, we have a weighted adjacency matrix A f (G) of G , in which the ij -entry is equal to f (d i , d j) if v i v j ∈ E (G) and 0 otherwise. In this paper, we use a unified approach to deal with the spectral properties of A f (G) for f (x , y) to be the functions of graphical or topological function-indices. Firstly, we obtain uniform interlacing inequalities for the weighted adjacency eigenvalues. For the edge-weight functions defined by almost a half of popularly used topological indices, it can be shown that our inequalities cannot be improved. Secondly, we establish a uniform equivalent condition for a connected graph G to have m distinct weighted adjacency eigenvalues. As an application, a combinatorial characterization for a graph to have two and three distinct weighted adjacency eigenvalues is presented, respectively. Moreover, bipartite graphs and unicyclic graphs with three distinct weighted adjacency eigenvalues are characterized. This paper attempts to unify the spectral study for weighted adjacency matrices of graphs with degree-based edge-weights. [ABSTRACT FROM AUTHOR]

A tree T $T$ is said to be even if all pairs of vertices of degree one in T $T$ are joined by a path of even length. We conjecture that every r $r$‐regular nonbipartite connected graph G $G$ has a spanning even tree and verify this conjecture when G $G$ has a 2‐factor. Well‐known results of Petersen and Hanson et al. imply that the only remaining unsolved case is when r $r$ is odd and G $G$ has at least r $r$ bridges. We investigate this case further and propose some related conjectures. [ABSTRACT FROM AUTHOR]

We consider the controllability of multi-agent dynamical systems modeled by a particular class of bipartite graphs, called chain graphs. Our main focus is related to chain graphs with exactly one repeated degree. We determine all chain graphs with this structural property and derive some properties of their Laplacian eigenvalues and associated eigenvectors. On the basis of the obtained theoretical results, we compute the minimum number of leading agents that make the system in question controllable and locate the leaders in the corresponding graph. Additionaly, we prove that a chain graph with exactly one repeated degree, that is not a star or a regular complete bipartite graph, has the second smallest Laplacian eigenvalue (also known as the algebraic connectivity) in (0.8299,1) and we show that the second smallest eigenvalue increases when the number of vertices increases. This result is of a particular interest in control theory, since families of controllable graphs whose algebraic connectivity is bounded from below model the systems with a small risk of power or communication failures. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

A connected graph G is H - removable if H is a subgraph of G , G has at least | V (H) | + 2 vertices and G − V (H ′) has a perfect matching for every subgraph H ′ of G isomorphic to H. So a connected graph is k K 2 -removable if and only if it is k -extendable, where k K 2 is a matching of size k. Further G is an H - forced graph if G − V (H ′) has a unique perfect matching for every subgraph H ′ of G isomorphic to H. In this paper, we first characterize k K 2 -forced graphs for k ≥ 2 as K 2 k + 2 and K k + 1 , k + 1 by using randomly matchable graphs. Let P i denote a path with i vertices. We show that P 3 - and P 4 -removable graphs are factor-critical and 1-extendable respectively. By using ear decomposition, we obtain that a connected graph G is P 3 -forced if and only if G is K 5 or C 2 k + 1 (k ≥ 2). Finally we prove that a connected graph G is P 4 -forced if and only if G is isomorphic to K 6 , K 3 , 3 , C 2 k (k ≥ 3), the Petersen graph, a uniform theta graph Θ 3 n (n ≥ 3) or C 12 +. [ABSTRACT FROM AUTHOR]

For a simple undirected connected graph G = (V, E), a maximal Roman dominating function (MRDF) of G is a function f : V (G) → {0, 1, 2} with the following properties: (i) For every vertex v ∈ {v ∈ V|f(v) = 0}, there exists a vertex u ∈ N(v) such that f(u) = 2. (ii) The set {v ∈ V|f(v) = 0} is not a dominating set of G; In other words, there exists a vertex v ∈ {v ∈ V|f(v) ≠ 0} such that N(v) ∩ {u ∈ V|f(u) = 0} ∅. The weight of an MRDF of G is the sum of its function values over all vertices, denoted as f(G) = ∑v∈V (G)f(v), and the maximal Roman domination number of G, denoted by γmR(G), is the minimum weight of an MRDF of G. In this paper, we establish some bounds of the maximal Roman domination number of graphs. Additionally, we develop an integer linear programming formulation to compute the maximal Roman domination number of any graph. Furthermore, we prove that maximal Roman domination problem (MRD) is NP-complete even restricted to star convex bipartite graphs and chordal bipartite graphs. Lastly, we show the maximal Roman domination number of threshold graphs, trees, and block graphs can be computed in linear time. [ABSTRACT FROM AUTHOR]

A connected nontrivial graph G is matching covered , if every edge of G is contained in a perfect matching of G. An edge e of a matching covered graph G is removable if G − e is still matching covered. Lovász and Plummer introduced removable edges in connection with ear decompositions of matching covered graphs. By characterizing the structure of removable edges, we obtain that the number of removable edges of Halin graphs G with even number of vertices, other than K 4 , C 6 ¯ and R 8 , is at least 1 4 (| V (G) | + 2) , and the lower bound is attainable. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix A (G) , and let τ (G) denote the smallest positive eigenvalue of A (G). Let G n be the class of all connected bipartite graphs on n = 2 k vertices with a unique perfect matching. In this article, we characterize the graphs G in G n such that τ (G) does not exceed 1 2. Using the above characterization, we obtain the unique graphs in G n with the maximum and the second maximum τ , respectively. Further, we prove that the largest and the second largest limit points of the smallest positive eigenvalues of bipartite graphs with a unique perfect matching are 1 2 and the reciprocal of α 3 1 2 + α 3 − 1 2 , respectively, where α 3 is the largest root of x 3 − x − 1. [ABSTRACT FROM AUTHOR]

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. A graph is said to be k(≥ 1)-extendable if every matching of size k can be extended to a perfect matching. It is known that the vertex connectivity of a 1-plane graph is at most 7. In this paper, we characterize the k-extendability of 7-connected maximal 1-plane graphs. We show that every 7-connected maximal 1-plane graph with even order is k-extendable for 1 ≤ k ≤ 3. And any 7-connected maximal 1-plane graph is not k-extendable for 4 ≤ k ≤ 11. As for k ≥ 12, any 7-connected maximal 1-plane graph with n vertices is not k-extendable unless n = 2k. [ABSTRACT FROM AUTHOR]

The distance energy of a connected graph G is the sum of absolute values of the eigenvalues of the distance matrix of G. In this paper, we study how the distance energy of the complete split graph G S (m , n) = K m + K ¯ n changes when an edge is deleted from it. The complete split graph G S (m , n) consists of a clique on m vertices and an independent set on n vertices in which each vertex of the clique is adjacent to each vertex of the independent set. We prove that the distance energy of the complete split graph G S (m , n) always increases when an edge is deleted from it. [ABSTRACT FROM AUTHOR]

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L (v) ⊆ V(H) for every v∈ V(G), a f:V(G)→ V(H) that preserves the edges (i.e., uv∈ E(G) implies f(u)f(v)∈ E(H)) and respects the lists (i.e., f(v)∈ L(v)). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time |V(H)|t⋅ n(1). Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H, we define irr(H) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S⊆ V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H. It follows from earlier results that if irr(H)=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H, the number of list homomorphisms from (G,L) to H — can be counted in time \(\operatorname{irr}(H)^t\cdot n^{\mathcal {O}(1)}\) if a tree decomposition of G having width at most t is given in the input, and, — given that \(\operatorname{irr}(H)\ge 2\) , cannot be counted in time \((\operatorname{irr}(H)-\varepsilon)^t\cdot n^{\mathcal {O}(1)}\) for any \(\varepsilon \gt 0\) , even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby, we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops. [ABSTRACT FROM AUTHOR]

A broadcast on a nontrivial connected graph G = (V,E) is a function f: V → {0, 1, . . ., d}, where d = diam(G), such that f(v) = e(v) (the eccentricity of v) for all v V. The weight of f is s(f) = P v∈V f(v). A vertex u hears f from v if f(v) > 0 and d(u, v) = f(v). A broadcast f is dominating if every vertex of G hears f. The upper broadcast domination number of G is Gb(G) = max {s(f): f is a minimal dominating broadcast of G} . A broadcast f is boundary independent if, for any vertex w that hears f from vertices v1, . . ., vk, k = 2, the distance d(w, vi) = f(vi) for each i. The maximum weight of a boundary independent broadcast is the boundary independence broadcast number abn(G). We compare abn to Gb, showing that neither is an upper bound for the other. We show that the differences Gb - abn and abn - Gb are unbounded, the ratio abn/Gb is bounded for all graphs, and Gb/abn is bounded for bipartite graphs but unbounded in general. [ABSTRACT FROM AUTHOR]

In this paper, we obtain necessary and sufficient conditions for decomposing tensor product of complete graphs into some connected unicyclic bipartite graphs with eight edges. [ABSTRACT FROM AUTHOR]

Let τ (G) and τ G (e) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G (e) = τ G (e) / τ (G) is called the spanning tree edge density, or simply density, of e. The maximum density dep (G) = max e ∈ E (G) d G (e) is called the spanning tree edge dependence, or simply dependence, of G. In 2016, Kahl made the following two conjectures. (C1) Let p , q be positive integers, p < q. There exists some function f (p , q) such that, if G is the bipartite construction as given in Theorem 3.5 (Theorem 2.1 in the present paper), then t i ≥ f (p , q) for all 2 ≤ i ≤ n implies that dep (G) = p / q. (C2) Let p , q be positive integers, p < q. There exists a planar graph G such that dep (G) = p / q. In this paper, by using combinatorial and electrical network approaches, firstly, we show (C1) is true. Secondly, we disprove (C2) by showing that for any planar graph G , dep (G) > 1 3 . On the other hand, by construction families of planar graphs, we show that, for p / q > 1 2 , there do exist a planar graph G such that dep (G) = p / q. Furthermore, we prove that the second conjecture holds for planar multigraphs. [ABSTRACT FROM AUTHOR]

Unmanned aerial vehicles (UAVs) have recently been widely employed as effective wireless platforms for aiding users in various situations, particularly in hard-to-reach scenarios like post-disaster relief efforts. This study employs multiple UAVs to cover users in overlapping locations, necessitating the optimization of UAV-user association to maximize the spectral and energy efficiency of the UAV network. Hence, a connected bipartite graph is formed between UAVs and users using graph theory to accomplish this goal. Then, a maximum weighted matching-based maximum flow (MwMaxFlow) optimization approach is proposed to achieve the maximum data rate given users' demands and the UAVs' maximum capacities. Additionally, power control is applied using the M -matrix theory to optimize users' transmit powers and improve their energy efficiency. The proposed strategy is evaluated and compared with other benchmark schemes through numerical simulations. The simulation outcomes indicate that the proposed approach balances spectral efficiency and energy consumption, rendering it suitable for various UAV wireless applications, including emergency response, surveillance, and post-disaster management. [ABSTRACT FROM AUTHOR]

The complex adjacency matrix A C (G) for a multidigraph G is introduced in Barik and Sahoo (AKCE Int J Graphs Comb 17(1):466–479, 2020). We study the rank of multidigraphs corresponding to the complex adjacency matrix and call it A C -rank. It is known that a connected graph G has rank 2 if and only if G is a complete bipartite graph, and has rank 3 if and only if it is a complete tripartite graph (Cheng in Electron J Linear Algebra 16:60–67, 2007). We observe that these results hold as special cases for multidigraphs but are not sufficient. In this article, we characterize all multidigraphs with A C -rank 2 and 3, respectively. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G. For any real number α ∈ [0,1], Nikiforov defined the Aα-matrix of G as Aα (G) = αD(G) + (1 - α)A(G). The eigenvalues of the matrix Aα(G) form the Aα-spectrum of G. The Aα-spectral radius of G is the largest eigenvalue of Aα(G) denoted by ρα(G). In this paper, we propose the Aα--matrix of G as Aα-(G) = αD(G) + (α - 1)A(G), 0 ≤ α ≤ 1. Let the Aα--spectral radius of G be denoted by λα-(G), and let Sβα(G) and Sβα- (G) be the sum of the βth powers of the Aα and Aα- eigenvalues of G, respectively. We determine the Aα--spectra of some graphs and obtain some bounds of the Aα--spectral radius. Moreover, we establish a relationship between the Aα-spectral radius and Aα--spectral radius. Indeed, for α ∈ (1/2, 1), we show that λα- ≤ ρα, and we prove that if G is connected, then the equality holds if and only if G is bipartite. Employing this relation, we obtain some upper bounds of λα- (G), and we prove that the Aα--spectrum and Aα-spectrum are equal if and only if G is a bipartite connected graph. Furthermore, we generalize the relation established by S. Akbari et al. in (2010) as follows: for α ∈ [1/2, 1), if 0 < β ≤ 1 or 2 ≤ β ≤ 3, then Sβα(G) ≥ Sβα- (G), and if 1 ≤ β ≤ 2, then Sβα(G) ≤ Sβα-(G), where the equality holds if and only if G is a bipartite graph such that β ∉ {1,2,3}. [ABSTRACT FROM AUTHOR]

Let G ˆ be a mixed graph and α ∈ [ 0 , 1 ]. Let D ˆ (G ˆ) and A ˆ (G ˆ) be the diagonal matrix of vertex degrees and the mixed adjacency matrix of G ˆ , respectively. The α -mixed adjacency matrix of G ˆ is the matrix A ˆ α (G ˆ) = α D ˆ (G ˆ) + (1 − α) A ˆ (G ˆ). We study some properties of A ˆ α (G ˆ) associated with some type of mixed graphs, namely quasi-bipartite and pre-bipartite mixed graphs. A spectral characterization for pre-bipartite and some class of quasi-bipartite mixed graphs is given. For a mixed graph G ˆ we exploit the problem of finding the smallest α for which A ˆ α (G ˆ) is positive semi-definite. This problem was proposed by Nikiforov in the context of undirected graphs. It is proven here that, for a mixed graph this number is not greater than 1 2 and that a connected mixed graph G ˆ with n ≥ 2 is quasi-bipartite if and only if this number is exactly 1 2. The spread of the α -mixed adjacency matrix is the difference among the largest and the smallest α -mixed adjacency eigenvalue. Upper and lower bounds for the spread of the α - mixed adjacency matrix are obtained. The α -mixed Estrada index of G ˆ is the sum of the exponentials of the eigenvalues of A ˆ α (G ˆ). In this paper, bounds for the eigenvalues of A ˆ α (G ˆ) are established and, using these bounds some sharp bounds on the mixed Estrada index of A ˆ α (G ˆ) are presented. [ABSTRACT FROM AUTHOR]

For a graph G with degree sequence (d 1 , d 2 , ... , d n) and a positive integer p , denote the degree power of G by e p (G) = ∑ i = 1 n d i p . In this paper, we concentrate on the extremal problems of degree powers in graphs with fixed size. By the majorization theory, we firstly characterize the graphs with the maximum e p (G) among all connected graphs in G (n , m) where m ≤ 2 n − 3. The second main result is about the graphs with forbidden cycles. Concretely, we determine the maximum e p (G) among all C ℓ -free graphs in G (m) and characterize the corresponding extremal graphs. An analogous result is obtained in non-bipartite graphs. Furthermore, we respectively give the sharp upper bounds on e p (G) in G (m) with respect to various graph parameters, such as clique number, chromatic number, girth, and circumference. [ABSTRACT FROM AUTHOR]

Quantum networks lead to novel notions of locality and correlations and an important problem concerns the question of which quantum states can be experimentally prepared with a given network structure and devices and which not. We prove that all multi-qubit graph states arising from a connected graph cannot originate from any quantum network with bipartite sources, as long as feed-forward and quantum memories are not available. Moreover, the fidelity of a multi-qubit graph state and any network state cannot exceed 9/10. Similar results can also be established for a large class of multi-qudit graph states. [ABSTRACT FROM AUTHOR]

The graph grabbing game is a two-player game on a connected graph with a weight function. In the game, they alternately remove a non-cut vertex from the graph (i.e., the resulting graph remains connected) and get the weight assigned to the vertex. Each player's aim is to maximize his or her outcome, when all vertices have been taken. Seacrest and Seacrest proved that if a given graph G is a tree with even order, then the first player can win the game for every weight function on G, and conjectured that the same statement holds if G is a connected bipartite graph with even order [D.E. Seacrest and T. Seacrest, Grabbing the gold, Discrete Math. 312 (2012) 1804-1806]. In this paper, we introduce a conjecture which is stated in terms of forbidden subgraphs and includes the above conjecture, and give two partial solutions to the conjecture. [ABSTRACT FROM AUTHOR]

The median of a graph G with weighted vertices is the set of all vertices x minimizing the sum of weighted distances from x to the vertices of G. For any integer p ≥ 2 , we characterize the graphs in which, with respect to any non-negative weights, median sets always induce connected subgraphs in the pth power G p of G. This extends some characterizations of graphs with connected medians (case p = 1 ) provided by Bandelt and Chepoi (SIAM J Discrete Math 15(2):268–282, 2002. https://doi.org/10.1137/S089548019936360X). The characteristic conditions can be tested in polynomial time for any p. We also show that several important classes of graphs in metric graph theory, including bridged graphs (and thus chordal graphs), graphs with convex balls, bucolic graphs, and bipartite absolute retracts, have G 2 -connected medians. Extending the result of Bandelt and Chepoi that basis graphs of matroids are graphs with connected medians, we characterize the isometric subgraphs of Johnson graphs and of halved-cubes with connected medians. [ABSTRACT FROM AUTHOR]

We say a class C of graphs is clean if for every positive integer t there exists a positive integer w (t) such that every graph in C with treewidth more than w (t) contains an induced subgraph isomorphic to one of the following: the complete graph K t , the complete bipartite graph K t , t , a subdivision of the (t × t) -wall or the line graph of a subdivision of the (t × t) -wall. In this paper, we adapt a method due to Lozin and Razgon (building on earlier ideas of Weißauer) to prove that the class of all H-free graphs (that is, graphs with no induced subgraph isomorphic to a fixed graph H) is clean if and only if H is a forest whose components are subdivided stars. Their method is readily applied to yield the above characterization. However, our main result is much stronger: for every forest H as above, we show that forbidding certain connected graphs containing H as an induced subgraph (rather than H itself) is enough to obtain a clean class of graphs. Along the proof of the latter strengthening, we build on a result of Davies and produce, for every positive integer η , a complete description of unavoidable connected induced subgraphs of a connected graph G containing η vertices from a suitably large given set of vertices in G. This is of independent interest, and will be used in subsequent papers in this series. [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]

An edge-locating coloring of a simple connected graph G is a partition of its edge set into matchings such that the vertices of G are distinguished by the distance to the matchings. The minimum number of the matchings of G that admits an edge-locating coloring is the edge-locating chromatic number of G, and denoted by χ'L(G). This paper introduces and studies the concept of edgelocating coloring. Graphs G with χ'L(G) ∈ {2, m} are characterized, where m is the size of G. We investigate the relationship between order, diameter and edge-locating chromatic number. We obtain the exact values of χ'L(Kn) and χ'L(Kn - M), where M is a maximum matching; indeed this result is also extended for any graph. We determine the edge-locating chromatic number of the join graphs of some well-known graphs. In particular, for any graph G, we show a relationship between χ'L(G + K1) and ∆(G). We investigate the edge-locating chromatic number of trees and present a characterization bound for any tree in terms of maximum degree, number of leaves, and the support vertices of trees. Finally, we prove that any edge-locating coloring of a graph is an edge distinguishing coloring. [ABSTRACT FROM AUTHOR]

A graceful labeling of a graph G with m edges consists in labeling the vertices of G with distinct integers from 0 to m such that each edge is uniquely identified by the absolute difference of the labels of its endpoints. In this work, we study the graceful labeling problem in the context of maker-breaker graph games. The Graceful Game was introduced by Tuza, in 2017, as a two-players game on a connected graph in which the players, Alice and Bob, take moves labeling the vertices with distinct integers from 0 to m. Players are constrained to use only legal labelings (moves), that is, after a move, all edge labels are distinct. Alice's goal is to obtain a graceful labeling for the graph, as Bob's goal is to prevent it from happening. In this work, we study winning strategies for Alice and Bob in graph classes: paths, complete graphs, cycles, complete bipartite graphs, caterpillars, trees, gear graphs, web graphs, prisms, hypercubes, 2-powers of paths, wheels and fan graphs. [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]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices, while the weight of a set of vertices is the sum of their weights. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). In what follows, all weights are real. Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition B X and B Y . Then B is generating if there exists an independent set S such that S ∪ B X and S ∪ B Y are both maximal independent sets of G. Generating subgraphs play an important role in finding WCW(G). In the restricted case that a generating subgraph B is isomorphic to K 1 , 1 , its unique edge is called a relating edge. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. This article deals with graphs G such that Δ (G) = | V (G) | - k for some k ∈ N . We prove that for this family recognizing well-covered graphs is a polynomial problem, while finding WCW(G) is co-NP-hard. To the best of our knowledge, this is the first family of graphs in the literature known to have these properties. For this set of graphs, recognizing relating edges and generating subgraphs is NP-complete. The article also deals with connected graphs for which δ (G) = k or δ (G) ≥ k - 1 k | V (G) | . For these families of graphs recognizing well-covered graphs is co-NP-complete, while recognizing relating edges is NP-complete. [ABSTRACT FROM AUTHOR]

Let G be a graph. A vertex-cut S of G is said to be k-restricted if every component of G − S has at least k vertices, and cyclic if G − S has at least two components which contain a cycle. The minimum cardinality over all k -restricted vertex-cuts of G is called the k-restricted connectivity of G and is denoted by κ k (G). Also the minimum cardinality over all cyclic vertex-cuts of G is called the cyclic connectivity of graph G and is denoted by κ c (G). In this paper, the k -restricted connectivity and cyclic connectivity of the direct product of two graphs G 1 and G 2 is obtained for some k ≥ 2 , where G 1 is a complete graph, and G 2 is a complete graph, a complete bipartite graph or a cycle. [ABSTRACT FROM AUTHOR]

For a simple graph G, the ABC-index is a degree based topological index and is defined as where dv is the degree of the vertex υ in G. Recently, the Laplacian ABC-matrix was introduced in [22] is defined by where is the diagonal matrix of ABC-degrees and Ã(G) is the ABC-matrix of G: The eigenvalues of the matrix are called the Laplacian ABC-eigenvalues of G. In the article, we consider the problem of characterization of connected graphs having exactly three distinct Laplacian ABC-eigenvalues. We solve this problem for bipartite graphs, multipartite graphs, unicyclic graphs, regular graphs and prove the non-existence of such graphs with diameter greater than 2. We introduce the concept of trace norm of the matrix called the Laplacian ABC-energy of G. We obtain some upper and lower bounds for the Laplacian ABC-energy and characterize the extremal graphs which attain these bounds. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. The eccentricity of a path P , denoted by ecc G (P) , is the maximum distance from P to any vertex in G. In the Central path (CP) problem, our aim is to find a path of minimum eccentricity. This problem was introduced by Cockayne et al., in 1981, in the study of different centrality measures on graphs. They showed that CP can be solved in linear time in trees, but it is known to be N P -hard in many classes of graphs such as chordal bipartite graphs, planar 3-connected graphs, split graphs, etc. We investigate the path eccentricity of a connected graph G as a parameter. Let pe (G) denote the value of ecc G (P) for a central path P of G. We obtain tight upper bounds for pe (G) in some graph classes. We show that pe (G) ≤ 1 on biconvex graphs and design an algorithm that finds such a path in linear time. On the other hand, by investigating the longest paths of a graph, we obtain tight upper bounds for pe (G) on arbitrary graphs and k -connected graphs. Finally, we study the relation between a central path and a longest path in a graph. We show that, on bipartite permutation graphs, a longest path is also a central path. Furthermore, for any such class of graphs, we exhibit a superclass that does not satisfy this property. • Every connected biconvex graph has a dominating path. • Tight upper bound for path eccentricity of arbitrary graphs. • Tight upper bound for path eccentricity of k-connected graphs, k ⩾ 2. [ABSTRACT FROM AUTHOR]

The graph grabbing game is played on a non-negatively weighted connected graph by Alice and Bob who alternately claim a non-cut vertex from the remaining graph, where Alice plays first, to maximize the weights on their respective claimed vertices at the end of the game when all vertices have been claimed. Seacrest and Seacrest conjectured that Alice can secure at least half of the total weight of every weighted connected bipartite even graph. Later, Egawa, Enomoto and Matsumoto partially confirmed this conjecture by showing that Alice wins the game on a class of weighted connected bipartite even graphs called Km,n-trees. We extend the result on this class to include a number of graphs, e.g. even blow-ups of trees and cycles. [ABSTRACT FROM AUTHOR]

The independence number α(G) $\alpha (G)$ and the dissociation number diss(G) $\text{diss}(G)$ of a graph G $G$ are the largest orders of induced subgraphs of G $G$ of maximum degree at most 0 and at most 1, respectively. We consider possible improvements of the obvious inequality 2α(G)≥diss(G) $2\alpha (G)\ge \text{diss}(G)$. For connected cubic graphs G $G$ distinct from K4 ${K}_{4}$, we show 5α(G)≥3diss(G) $5\alpha (G)\ge 3\,\text{diss}(G)$, and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle‐free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs. [ABSTRACT FROM AUTHOR]

The matching number of G, written α ′ (G) , is the size of a maximum matching in G. Suppose that n and k are positive integers of the same parity. Let θ ′ (n , k) be the largest root of x 3 − (n − k − 2) x 2 − (n − 1) x + k (n − k − 2) = 0 and θ (n , k) = { θ ′ (n , k) if n ≥ 3 k + 2 n − k − 2 + (n − k − 2) 2 + 4 (n 2 − k 2) 4 if n ≤ 3 k . In this article, we prove that for a positive integer n ≥ k + 2 , if G is an n-vertex connected graph with the spectral radius ρ (G) > θ (n , k) , then α ′ (G) > n − k 2 . The bound is sharp in the sense that for every positive integer n ≥ k + 2 , there are graphs H with ρ (H) = θ (n , k) and α ′ (G) = n − k 2 . [ABSTRACT FROM AUTHOR]

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph G is a pair G = (V , E), where V and E are the vertex set and the edge set of G , respectively. The order and size of G is the number of vertices and edges of G , respectively. The degree or valency of a vertex u in a graph G (loopless), denoted by deg (u), is the number of edges meeting at u. If, for every vertex ν in G , deg (ν) = k , we say that G is a k -regular graph. The cycle of order n is denoted by Cn and is a connected 2-regular graph. The path graph of order n is denoted by Pn and obtain by deleting an edge of Cn. A tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected undirected graph without cycle. A leaf (or pendant vertex) of a tree is a vertex of the tree of degree 1. An edge of a graph is said to be pendant if one of its vertices is a pendant vertex. A complete bipartite graph is a graph G with and such that every vertex of the set (part) X is connected to every vertex of the set (part) Y. If , then this graph is denoted by Km,n. The complete bipartite graph K1,n is called the star graph which has n + 1 vertices. The distance between two vertices u and ν of G , denoted by d (u , ν), is defined as the minimum number of edges of the walks between them. The complement of graph G is denoted by and is a graph with the same vertices such that two distinct vertices of are adjacent if, and only if, they are not adjacent in G. For more information on graphs, refer to [1]. [ABSTRACT FROM AUTHOR]

We establish various nodal domain theorems for p-Laplacians on signed graphs, which unify most of the existing results on nodal domains of graph p-Laplacians and arbitrary symmetric matrices. Based on our nodal domain estimates, we obtain a higher order Cheeger inequality that relates the variational eigenvalues of p-Laplacians and Atay-Liu's multi-way Cheeger constants on signed graphs. In the particular case of p D 1, this leads to several identities relating variational eigenvalues and multi-way Cheeger constants. Intriguingly, our approach also leads to new results on usual graphs, including a weak version of Sturm's oscillation theorem for graph 1-Laplacians and nonexistence of eigenvalues between the largest and second largest variational eigenvalues of p-Laplacians with p >1 on connected bipartite graphs. [ABSTRACT FROM AUTHOR]

Summary: Sparse neural networks are shown to give accurate predictions competitive to denser versions, while also minimizing the number of arithmetic operations performed. However current GPU hardware can only exploit structured sparsity patterns for better efficiency. We propose a framework for generating structured multilevel block sparse neural networks by using the theory of graph products. Our Ramanujan bipartite graph product (RBGP) framework uses products of Ramanujan graphs to obtain the best connectivity for a given level of sparsity. This essentially ensures that the i.) the networks has the structured block sparsity for which runtime efficient algorithms exists, ii.) the model gives high prediction accuracy, due to the better expressive power derived from the connectivity of the graph, iii.) the graph data structure has a succinct representation that can be stored efficiently in memory. We use our framework to design a specific connectivity pattern called RBGP4 which makes efficient use of the memory hierarchy available on GPU. We benchmark our approach on image classification and machine translation tasks with an edge (Jetson Nano 2GB) as well as server (V100) GPUs. When compared with commonly used sparsity patterns like unstructured and block, we obtain significant speedups while achieving the same level of accuracy. [ABSTRACT FROM AUTHOR]