Maximum Degree Energy and Minimum Degree Energy in the Context of Some Graph Operations

The Maximum Number of Triangles in Graphs Without Cycles of Length 0mod5

For a graph and a graph family , let denote the maximum number of copies of in an ‐free ‐vertex graph. Let . Bai, Tompkins, and Well conjectured that is attained if and each block of the graph is a . In this paper, we determine the exact value of and the extremal graphs for all . The novelty of our proof is to give a proper partition of the set of triangles in an extremal graph. On the basis of this partition, we obtain the partition of the edge set and thus the structure of an extremal graph. Our new method can also be applied to obtain some meaningful results in other settings.

Laplacian Minimum Domination Energy of Some Derived Graphs

Graph energy is an important concept in spectral graph theory with applications in mathematics and chemistry. In this paper, we study the Laplacian minimum domination energy of derived graphs of some standard graphs. The main aim is to obtain formulas, properties, and bounds for this energy measure. The study considers derived graphs of star graphs, complete bipartite graphs, friendship graphs, and healthy spider graphs. Using minimum dominating sets, minimum domination adjacency matrices, and Laplacian minimum domination matrices, the eigenvalues of these derived graphs are determined. Based on these eigenvalues, explicit formulas for the Laplacian minimum domination energy are obtained. Further, some basic properties related to eigenvalues are established. Upper and lower bounds for the Laplacian minimum domination energy are also derived using matrix methods and classical inequalities such as the Cauchy-Schwarz inequality. The results extend existing work on graph energy by combining domination concepts, Laplacian matrices, and derived graphs. The formulas, properties, and bounds obtained in this paper provide a better understanding of the spectral behavior of derived graphs and may be useful for further research in graph theory and its applications.

Positive Square Energy of Graphs with Minimum Degree at Least Two

Let $s^+(G)$ denote the sum of the squares of the positive adjacency eigenvalues of a graph $G$. The square-energy conjecture of Elphick, Farber, Goldberg, and Wocjan, proved by Liu, Tang, and Zhang, gives a lower bound of $n-1$ for any connected graph of order $n$. We strengthen this bound to $s^+(G)\ge n$ for every connected graph $G$ of order $n$ with minimum degree at least two, unless $G$ is a cycle.

Theory & Applications of Graphs Theory & Applications of Graphs

On the maximum weight convex problem for some geometric graph-convexities

For a given geometric graph-convexity on a graph $G$ equipped with a weight function on the vertices with value in $\mathbb{Z}$, the Max Weight Convex Set problem consists in determining the convex set $S$ with maximum weight (sum of the weight of the vertices in $S$). Although the problem is NP-complete in general, it remains polynomial for particular cases. After a survey of known results, our main contribution uses a generalisation of the maximum subsequence problem to laminar trees. Then we derive a linear algorithm for proper interval graphs and a quadratic one for interval graphs. Both improve the state of the art.

Rigidity of complements of bounded-degree graphs

Maxwell observed that the graph of any rigid generic framework in $\mathbb{R}^d$ on $n$ vertices has at least $dn-\binom{d+1}{2}$ edges. In this article we prove that graphs whose complement has maximum degree at most two and no component isomorphic to a triangle or a square are rigid in the maximum dimension allowed by this observation. In particular, this determines the precise maximum dimension in which the graph obtained from a complete graph $K_{2m}$ by deleting a perfect matching is rigid, resolving a recent conjecture of Lew. We also deduce bounds on the rigidity of complements of bounded-degree graphs more generally, which significantly improve existing degree-based bounds.