Ivan Damnjanović

Search for another author

Author Description

Ask a Question About This Mathematician

All published works (37)

On cubic polycirculant nut graphs

2025-05-06

Nino Bašić , Ivan Damnjanović

Classification of quartic bicirculant nut graphs

2025-02-10

Ivan Damnjanović , Nino Bašić , Tomaž Pisanski +1 more

A graph is called a nut graph if zero is its eigenvalue of multiplicity one and its corresponding eigenvector has no zero entries. A graph is a bicirculant if it … A graph is called a nut graph if zero is its eigenvalue of multiplicity one and its corresponding eigenvector has no zero entries. A graph is a bicirculant if it admits an automorphism with two equally sized vertex orbits. There are four classes of connected quartic bicirculant graphs. We classify the quartic bicirculant graphs that are nut graphs by investigating properties of each of these four classes.

Chat View PDF

Some bounds on the spectral radius of connected threshold graphs

2024-12-20

Péter Csíkvári , Ivan Damnjanović , Dragan Stevanović +1 more

The spectral radius of a graph is the spectral radius of its adjacency matrix. A threshold graph is a simple graph whose vertices can be ordered as $v_1, v_2, \ldots, … The spectral radius of a graph is the spectral radius of its adjacency matrix. A threshold graph is a simple graph whose vertices can be ordered as $v_1, v_2, \ldots, v_n$, so that for each $2 \le i \le n$, vertex $v_i$ is either adjacent or nonadjacent simultaneously to all of $v_1, v_2, \ldots, v_{i-1}$. Brualdi and Hoffman initially posed and then partially solved the extremal problem of finding the simple graphs with a given number of edges that have the maximum spectral radius. This problem was subsequently completely resolved by Rowlinson. Here, we deal with the similar problem of maximizing the spectral radius over the set of connected simple graphs with a given number of vertices and edges. As shown by Brualdi and Solheid, each such extremal graph is necessarily a threshold graph. We investigate the spectral radii of threshold graphs by relying on computations involving lazy walks. Furthermore, we obtain three lower bounds and one upper bound on the spectral radius of a given connected threshold graph.

Chat View PDF

Some properties of the <i>q</i> -numerical radius

2024-12-07

Hranislav Stanković , Mihailo Krstić , Ivan Damnjanović

In the given study, we consider the q-numerical radius ωq(⋅) of operator matrices defined on a direct sum of Hilbert spaces and investigate the various inequalities involving these values. We … In the given study, we consider the q-numerical radius ωq(⋅) of operator matrices defined on a direct sum of Hilbert spaces and investigate the various inequalities involving these values. We also prove that supn∈Nωq(An)⩽ωq(⨁n=1+∞An)⩽|q|+21−|q|2|q|supn∈Nωq(An) for all the q∈C∖{0},|q|⩽1, thereby extending the well known equality regarding the numerical radii that occurs when we plug in q = 1. Subsequently, we give explicit formulae for computing ωq(⋅) for some special cases of operator matrices. Finally, we establish some analytical properties of ωq(⋅) regarded as a function in q.

On cubic polycirculant nut graphs

2024-11-25

Nino Bašić , Ivan Damnjanović

A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an $\ell$-circulant graph is a graph … A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an $\ell$-circulant graph is a graph that admits a cyclic group of automorphisms having $\ell$ vertex orbits of equal size. It is not difficult to observe that there exists no cubic $1$-circulant nut graph or cubic $2$-circulant nut graph, while the full classification of all the cubic $3$-circulant nut graphs was recently obtained [Electron. J. Comb. 31(2) (2024), #2.31]. Here, we investigate the existence of cubic $\ell$-circulant nut graphs for $\ell \ge 4$ and show that there is no cubic $4$-circulant nut graph or cubic $5$-circulant nut graph by using a computer-assisted proof. Furthermore, we rely on a construction based approach in order to demonstrate that there exist infinitely many cubic $\ell$-circulant nut graphs for any fixed $\ell \in \{6, 7 \}$ or $\ell \ge 9$.

Chat View PDF

On the degrees of regular nut graphs

2024-10-17

Nino Bašić , Ivan Damnjanović , Patrick W. Fowler

A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no zero entry. It is known … A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no zero entry. It is known that infinitely many $d$-regular nut graphs exist for $3 \leq d \leq 12$ and for $d \geq 4$ such that $d \equiv 0 \pmod{4}$. Here it is shown that infinitely many $d$-regular nut graphs exist for each degree $d \geq 3$.

Chat View PDF

Polynomial indicator of flat bands

2024-10-12

Ivan Damnjanović , Milan Damnjanović , I. Milošević +1 more

We present a universal and straightforward algebraic procedure for flat bands construction, polynomial indicator method. Using only Bloch Hamiltonian eigendeterminant functional to identify conditions that guarantee existence of nondispersive eigenvalues, … We present a universal and straightforward algebraic procedure for flat bands construction, polynomial indicator method. Using only Bloch Hamiltonian eigendeterminant functional to identify conditions that guarantee existence of nondispersive eigenvalues, the polynomial indicator method is applicable to all lattice types, enabling predictions of (topological) flat bands in electronic band structure (across the materials), as well as all possible designs of novel artificial flat band lattices. The method is in detail illustrated on several examples - kagome and dice lattice included.

Chat View PDF

On transmission-irregular graphs and long pendent paths

2024-07-31

Ivan Damnjanović , Dragan Stevanović , Salem Al-Yakoob

Characterization of transmission irregular starlike and double starlike trees

2024-05-30

Ivan Damnjanović

Counting the number of inequivalent arithmetic expressions on $n$ variables

2024-05-22

Ivan Stošić , Ivan Damnjanović , Žarko Ranđelović

An expression is any mathematical formula that contains certain formal variables and operations to be executed in a specified order. In computer science, it is usually convenient to represent each … An expression is any mathematical formula that contains certain formal variables and operations to be executed in a specified order. In computer science, it is usually convenient to represent each expression in the form of an expression tree. Here, we consider only arithmetic expressions, i.e., those that contain only the four standard arithmetic operations: addition, subtraction, multiplication and division, alongside additive inversion. We first provide certain theoretical results concerning the equivalence of such expressions and then disclose a $\Theta(n^2)$ algorithm that computes the number of inequivalent arithmetic expressions on $n$ distinct variables.

Chat View PDF

Classification of Cubic Tricirculant Nut Graphs

2024-05-16

Ivan Damnjanović , Nino Bašić , Tomaž Pisanski +1 more

A nut graph is a simple graph whose adjacency matrix has the eigenvalue zero with multiplicity one such that its corresponding eigenvector has no zero entries. It is known that … A nut graph is a simple graph whose adjacency matrix has the eigenvalue zero with multiplicity one such that its corresponding eigenvector has no zero entries. It is known that there exist no cubic circulant nut graphs. A bicirculant (resp. tricirculant) graph is defined as a graph that admits a cyclic group of automorphisms having two (resp. three) orbits of vertices of equal size. We show that there exist no cubic bicirculant nut graphs and we provide a full classification of cubic tricirculant nut graphs.

Chat View PDF

Solving the Mostar index inverse problem

2024-02-28

Yaser Alizadeh , Nino Bašić , Ivan Damnjanović +4 more

An inverse result for Wang’s theorem on extremal trees

2024-01-01

Ivan Damnjanović , Zarko Randjelovic

It was recently noted by Damnjanovi?c et al. [MATCH Commun. Math. Comput. Chem. 90 (2023), 197?202] that the problem of finding a tree which minimises or maximises the Sombor index … It was recently noted by Damnjanovi?c et al. [MATCH Commun. Math. Comput. Chem. 90 (2023), 197?202] that the problem of finding a tree which minimises or maximises the Sombor index among all the trees with a given degree sequence fits within the framework of results by Hua Wang from [Cent. Eur. J. Math. 12 (2014), 1656?1663]. Here, we extend these results by providing an inverse for the aforementioned theorem by Wang. In other words, for any fixed symmetric function f satisfying a monotonicity condition that f (x, a) + f (y, b) > f (y, a) + f (x, b) for any x > y and a > b, we characterise precisely the set of all the trees minimising or maximising the sum f (deg x, deg y) over all the adjacent pairs of vertices x and y, among the trees with a given degree sequence.

Chat View PDF

Complete resolution of the circulant nut graph order–degree existence problem

2023-10-23

Ivan Damnjanović

A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is a circulant matrix whose null space is spanned by a single vector without zero elements. … A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is a circulant matrix whose null space is spanned by a single vector without zero elements. Regarding these graphs, the order–degree existence problem can be thought of as the mathematical problem of determining all the possible pairs (n, d) for which there exists a d-regular circulant nut graph of order n. This problem was initiated by Bašić et al. and the first major results were obtained by Damnjanović and Stevanović, who proved that for each odd t ≥ 3 such that t ≢10 1 and t ≢18 15, there exists a 4t-regular circulant nut graph of order n for each even n ≥ 4t + 4. Afterwards, Damnjanović improved these results by showing that there necessarily exists a 4t-regular circulant nut graph of order n whenever t is odd, n is even, and n ≥ 4t + 4 holds, or whenever t is even, n is such that n ≡4 2, and n ≥ 4t + 6 holds. In this paper, we extend the aforementioned results by completely resolving the circulant nut graph order–degree existence problem. In other words, we fully determine all the possible pairs (n, d) for which there exists a d-regular circulant nut graph of order n.

Chat View PDF

A note on Cayley nut graphs whose degree is divisible by four

2023-01-01

Ivan Damnjanović

A nut graph is a non-trivial simple graph such that its adjacency matrix has a one-dimensional null space spanned by a full vector. It was recently shown by the authors … A nut graph is a non-trivial simple graph such that its adjacency matrix has a one-dimensional null space spanned by a full vector. It was recently shown by the authors that there exists a $d$-regular circulant nut graph of order $n$ if and only if $4 \mid d, \, 2 \mid n, \, d > 0$, together with $n \ge d + 4$ if $d \equiv_8 4$ and $n \ge d + 6$ if $8 \mid d$, as well as $(n, d) \neq (16, 8)$ [arXiv:2212.03026, 2022]. In this paper, we demonstrate the existence of a $d$-regular Cayley nut graph of order $n$ for each $4 \mid d, \, d > 0$ and $2 \mid n, \, n \ge d + 4$, thereby resolving the existence problem for Cayley nut graphs and vertex-transitive nut graphs whose degree is divisible by four.

Chat View PDF

An alternative proof of the Sombor index minimizing property of greedy trees

2023-01-01

Ivan Damnjanović , Dragan Stevanović

Recently, Gutman defined a new graph invariant which is named the Sombor index SO(G) of a graph G and is computed via the expression SO(G) = ?u~v? qdeg(u)2 + deg(v)2, … Recently, Gutman defined a new graph invariant which is named the Sombor index SO(G) of a graph G and is computed via the expression SO(G) = ?u~v? qdeg(u)2 + deg(v)2, where deg(u) represents the degree of the vertex u in G and the summing is performed across all the unordered pairs of adjacent vertices u and v. Damnjanovic et al. have implemented an earlier result obtained by Wang in order to show that, among all the trees TD that have a specified degree sequence D, the greedy tree must attain the minimum Sombor index. Here we provide an alternative proof of this same result by constructing an auxiliary graph invariant named the pseudo-Sombor index and without relying on any other earlier results.

Chat View PDF

Characterization of transmission irregular starlike and double starlike trees

2023-01-01

Ivan Damnjanović

The transmission of a vertex in a connected graph is the sum of its distances to all the other vertices. A graph is transmission irregular (TI) when all of its … The transmission of a vertex in a connected graph is the sum of its distances to all the other vertices. A graph is transmission irregular (TI) when all of its vertices have mutually distinct transmissions. In an earlier paper, Al-Yakoob and Stevanovi\'c [Appl. Math. Comput. 380 (2020), 125257] gave the full characterization of TI starlike trees with three branches. Here, we improve these results by using a different approach to provide the complete characterization of all TI starlike trees. Moreover, we find the precise conditions under which a double starlike tree is TI. Finally, we implement the aforementioned conditions in order to find several infinite families of TI starlike trees and TI double starlike trees.

Chat View PDF

Solving the Mostar index inverse problem

2023-01-01

Yaser Alizadeh , Nino Bašić , Ivan Damnjanović +4 more

A nonnegative integer $p$ is realizable by a graph-theoretical invariant $I$ if there exist a graph $G$ such that $I(G) = p$. The inverse problem for $I$ consists of finding … A nonnegative integer $p$ is realizable by a graph-theoretical invariant $I$ if there exist a graph $G$ such that $I(G) = p$. The inverse problem for $I$ consists of finding all nonnegative integers $p$ realizable by $I$. In this paper, we consider and solve the inverse problem for the Mostar index, a recently introduced graph-theoretical invariant which attracted a lot of attention in recent years in both the mathematical and the chemical community. We show that a nonnegative integer is realizable by the Mostar index if and only if it is not equal to one. Besides presenting the complete solution to the problem, we also present some empirical observations and outline several open problems and possible directions for further research.

Chat View PDF

Classification of cubic tricirculant nut graphs

2023-01-01

Ivan Damnjanović , Nino Bašić , Tomaž Pisanski +1 more

Chat View PDF

Two families of circulant nut graphs

2023-01-01

Ivan Damnjanović

A circulant nut graph is a non-trivial simple graph whose adjacency matrix is a circulant matrix of nullity one such that its non-zero null space vectors have no zero elements. … A circulant nut graph is a non-trivial simple graph whose adjacency matrix is a circulant matrix of nullity one such that its non-zero null space vectors have no zero elements. The study of circulant nut graphs was originally initiated by Basic et al. [Art Discrete Appl. Math. 5(2) (2021) #P2.01], where a conjecture was made regarding the existence of all the possible pairs (n, d) for which there exists a d-regular circulant nut graph of order n. Later on, it was proved by Damnjanovic and Stevanovic [Linear Algebra Appl. 633 (2022) 127-151] that for each odd t ? 3 such that t ?/10 1 and t ?/18 15, the 4t-regular circulant graph of order n with the generator set {1, 2, 3,..., 2t+1}\{t}) must necessarily be a nut graph for each even n ? 4t + 4. In this paper, we extend these results by constructing two families of circulant nut graphs. The first family comprises the 4t-regular circulant graphs of order n which correspond to the generator sets {1, 2,..., t?1} ? {n/4, n/4 + 1} ? {n/2?(t?1),..., n/2 ? 2, n/2 ? 1}, for each odd t ? N and n ? 4t + 4 divisible by four. The second family consists of the 4t-regular circulant graphs of order n which correspond to the generator sets {1, 2,..., t?1} ? {n+2/4, n+6/4} ? {n/2 ?(t?1),..., n/2?2, n/2?1}, for each t ? N and n ? 4t + 6 such that n ?4 2. We prove that all of the graphs which belong to these families are indeed nut graphs, thereby fully resolving the 4t-regular circulant nut graph order-degree existence problem whenever t is odd and partially solving this problem for even values of t as well.

Chat View PDF

Spectral properties of balanced trees and dendrimers

2022-10-26

Ivan Damnjanović , Slobodan Filipovski , Dragan Stevanović

Chat View PDF

Assigned rational functions of a rooted tree

2022-01-01

Ivan Damnjanović

We investigate the spectral properties of rooted trees with the intention of improving the currently existing results that deal with this matter. The concept of an assigned rational function is … We investigate the spectral properties of rooted trees with the intention of improving the currently existing results that deal with this matter. The concept of an assigned rational function is recursively defined for each vertex of a rooted tree. Afterwards, two mathematical formulas are given which show how the characteristic polynomials of the adjacency and Laplacian matrix can be represented as products of the aforementioned rational functions. In order to demonstrate their general use case scenario, the obtained formulas are subsequently implemented on balanced trees, with a special focus on the Bethe trees. In the end, some of the previously derived results are used in order to construct a tree merging procedure which preserves the spectra of all of the starting trees.

Chat View PDF

Two families of circulant nut graphs

2022-01-01

Ivan Damnjanović

A circulant nut graph is a non-trivial simple graph whose adjacency matrix is a circulant matrix of nullity one such that its non-zero null space vectors have no zero elements. … A circulant nut graph is a non-trivial simple graph whose adjacency matrix is a circulant matrix of nullity one such that its non-zero null space vectors have no zero elements. The study of circulant nut graphs was originally initiated by Ba\v{s}i\'c et al. [Art Discrete Appl. Math. 5(2) (2021) #P2.01], where a conjecture was made regarding the existence of all the possible pairs $(n, d)$ for which there exists a $d$-regular circulant nut graph of order $n$. Later on, it was proved by Damnjanovi\'c and Stevanovi\'c [Linear Algebra Appl. 633 (2022) 127-151] that for each odd $t \ge 3$ such that $t\not\equiv_{10}1$ and $t\not\equiv_{18}15$, the $4t$-regular circulant graph of order $n$ with the generator set $\{ 1, 2, 3, \ldots, 2t+1 \} \setminus \{t\})$ must necessarily be a nut graph for each even $n \ge 4t + 4$. In this paper, we extend these results by constructing two families of circulant nut graphs. The first family comprises the $4t$-regular circulant graphs of order $n$ which correspond to the generator sets $\{1, 2, \ldots, t-1\} \cup \left\{\frac{n}{4}, \frac{n}{4} + 1 \right\} \cup \left\{\frac{n}{2} - (t-1), \ldots, \frac{n}{2} - 2, \frac{n}{2} - 1 \right\}$, for each odd $t \in \mathbb{N}$ and $n \ge 4t + 4$ divisible by four. The second family consists of the $4t$-regular circulant graphs of order $n$ which correspond to the generator sets $\{1, 2, \ldots, t-1\} \cup \left\{\frac{n+2}{4}, \frac{n+6}{4} \right\} \cup \left\{\frac{n}{2} - (t-1), \ldots, \frac{n}{2} - 2, \frac{n}{2}-1 \right\}$, for each $t \in \mathbb{N}$ and $n \ge 4t + 6$ such that $n \equiv_{4} 2$. We prove that all of the graphs which belong to these families are indeed nut graphs, thereby fully resolving the $4t$-regular circulant nut graph order-degree existence problem whenever $t$ is odd and partially solving this problem for even values of $t$ as well.

Chat View PDF

Spectral properties of balanced trees and dendrimers

2022-01-01

Ivan Damnjanović , Slobodan Filipovski , Dragan Stevanović

We investigate the spectral properties of balanced trees and dendrimers, with a view toward unifying and improving the existing results. Here we find a semi-factorized formula for their characteristic polynomials. … We investigate the spectral properties of balanced trees and dendrimers, with a view toward unifying and improving the existing results. Here we find a semi-factorized formula for their characteristic polynomials. Afterwards, we determine their spectra via the aforementioned factors. In the end, we analyze the behavior of the energy of dendrimers and compute lower and upper bound approximations for it.

Chat View PDF

Greedy trees have minimum Sombor indices

2022-01-01

Ivan Damnjanović , Dragan Stevanović

Recently, Gutman [MATCH Commun. Math. Comput. Chem. 86 (2021) 11-16] defined a new graph invariant which is named the Sombor index $\mathrm{SO}(G)$ of a graph $G$ and is computed via … Recently, Gutman [MATCH Commun. Math. Comput. Chem. 86 (2021) 11-16] defined a new graph invariant which is named the Sombor index $\mathrm{SO}(G)$ of a graph $G$ and is computed via the expression \[ \mathrm{SO}(G) = \sum_{u \sim v} \sqrt{\mathrm{deg}(u)^2 + \mathrm{deg}(v)^2} , \] where $\mathrm{deg}(u)$ represents the degree of the vertex $u$ in $G$ and the summing is performed across all the unordered pairs of adjacent vertices $u$ and $v$. Here we take into consideration the set of all the trees $\mathcal{T}_D$ that have a specified degree sequence $D$ and show that the greedy tree attains the minimum Sombor index on the set $\mathcal{T}_D$.

Chat View PDF

A note on extremal Sombor indices of trees with a given degree sequence

2022-01-01

Ivan Damnjanović , Marko V. Milošević , Dragan Stevanović

We note here that the problem of determining extremal values of Sombor index for trees with a given degree sequence fits within the framework of results by Hua Wang from … We note here that the problem of determining extremal values of Sombor index for trees with a given degree sequence fits within the framework of results by Hua Wang from [Cent. Eur. J. Math. 12 (2014) 1656-1663], implying that the greedy tree has the minimum Sombor index, while an alternating greedy tree has the maximum Sombor index.

Chat View PDF

Complete resolution of the circulant nut graph order-degree existence problem

2022-01-01

Ivan Damnjanović

A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is a circulant matrix whose null space is spanned by a single vector without zero elements. … A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is a circulant matrix whose null space is spanned by a single vector without zero elements. Regarding these graphs, the order-degree existence problem can be thought of as the mathematical problem of determining all the possible pairs $(n, d)$ for which there exists a $d$-regular circulant nut graph of order $n$. This problem was initiated by Ba\v{s}i\'c et al. and the first major results were obtained by Damnjanovi\'c and Stevanovi\'c, who proved that for each odd $t \ge 3$ such that $t\not\equiv_{10}1$ and $t\not\equiv_{18}15$, there exists a $4t$-regular circulant nut graph of order $n$ for each even $n \ge 4t + 4$. Afterwards, Damnjanovi\'c improved these results by showing that there necessarily exists a $4t$-regular circulant nut graph of order $n$ whenever $t$ is odd, $n$ is even, and $n \ge 4t + 4$ holds, or whenever $t$ is even, $n$ is such that $n \equiv_4 2$, and $n \ge 4t + 6$ holds. In this paper, we extend the aforementioned results by completely resolving the circulant nut graph order-degree existence problem. In other words, we fully determine all the possible pairs $(n, d)$ for which there exists a $d$-regular circulant nut graph of order $n$.

Chat View PDF

An inverse result for Wang's theorem on extremal trees

2022-01-01

Ivan Damnjanović

Among all trees on $n$ vertices with a given degree sequence, how do we maximise or minimise the sum over all adjacent pairs of vertices $x$ and $y$ of $f(\mathrm{deg} … Among all trees on $n$ vertices with a given degree sequence, how do we maximise or minimise the sum over all adjacent pairs of vertices $x$ and $y$ of $f(\mathrm{deg} x, \mathrm{deg} y)$? Here $f$ is a fixed symmetric function satisfying a 'monotonicity' condition that \[ f(x, a) + f(y, b) > f(y, a) + f(x, b) \quad \mbox{for any $x > y$ and $a > b$} . \] These functions arise naturally in several areas of graph theory, particularly chemical graph theory. Wang showed that the so-called 'greedy' tree maximises this quantity, while an 'alternating greedy' tree minimises it. Our aim in this paper is to solve the inverse problem: we characterise precisely which trees are extremal for these two problems.

Chat View PDF

On the nullities of quartic circulant graphs and their extremal null spaces

2022-01-01

Ivan Damnjanović

A circulant graph is a simple graph whose adjacency matrix can be represented in the form of a circulant matrix, while a nut graph is considered to be a graph … A circulant graph is a simple graph whose adjacency matrix can be represented in the form of a circulant matrix, while a nut graph is considered to be a graph whose null space is spanned by a single full vector. In a previous study by Damnjanovi\'c [arXiv:2212.03026, 2022], the complete set of all the pairs $(n, d)$ for which there exists a $d$-regular circulant nut graph of order $n$ has been determined. Motivated by the said results, we put our focus on the quartic circulant graphs and derive an explicit formula for computing their nullities. Furthermore, we implement the aforementioned formula in order to obtain a method for inspecting the singularity of a particular quartic circulant graph and find the concise criteria to be used for testing whether such a graph is a nut graph. Subsequently, we compute the minimum and maximum nullity that a quartic circulant graph of a fixed order $n$ can attain, for each viable order $n \ge 5$. Finally, we determine all the graphs attaining these nullities and then provide a full characterization of all of their corresponding extremal null spaces.

Chat View PDF

Finding counterexamples for a conjecture of Akbari, Alazemi and Andjeli\'c

2021-11-30

Đorđe Stevanović , Ivan Damnjanović , Dragan Stevanović

For a graph $G$, its energy $\mathcal{E}(G)$ is the sum of absolute values of the eigenvalues of its adjacency matrix, the matching number $\mu(G)$ is the number of edges in … For a graph $G$, its energy $\mathcal{E}(G)$ is the sum of absolute values of the eigenvalues of its adjacency matrix, the matching number $\mu(G)$ is the number of edges in a maximum matching of $G$, while $\Delta$ is the maximum vertex degree of $G$. Akbari, Alazemi and An{\dj}eli\'c in [Appl. Anal. Discrete Math. 15 (2021), 444--459] proved that $\mathcal{E}(G) \leq 2\mu(G)$ when $G$ is connected and $\Delta\geq6$, and conjectured that the same inequality is also valid when $2\leq\Delta\leq5$. Here we first computationally enumerate small counterexamples for this conjecture and then provide two infinite families of counterexamples.

Finding counterexamples for a conjecture of Akbari, Alazemi and Andjeli\'c

2021-11-30

Đorđe Stevanović , Ivan Damnjanović , Dragan Stevanović

Chat View PDF

On circulant nut graphs

2021-10-18

Ivan Damnjanović , Dragan Stevanović

On circulant nut graphs

2021-04-21

Ivan Damnjanović , Dragan Stevanović

A nut graph is a simple graph whose adjacency matrix has the eigenvalue~0 with multiplicity~1 such that its corresponding eigenvector has no zero entries. Motivated by a question of Fowler … A nut graph is a simple graph whose adjacency matrix has the eigenvalue~0 with multiplicity~1 such that its corresponding eigenvector has no zero entries. Motivated by a question of Fowler et al.~[\emph{Disc. Math. Graph Theory} 40 (2020), 533--557] to determine the pairs $(n,d)$ for which a vertex-transitive nut graph of order $n$ and degree $d$ exists, Ba\v sic et al. [\arxiv{2102.04418}, 2021] initiated the study of circulant nut graphs. Here we first show that the generator set of a circulant nut graph necessarily contains equally many even and odd integers. Then we characterize circulant nut graphs with the generator set $\{x,x+1,\dots,x+2t-1\}$ for $x,t\in\N$, which generalizes the result of Ba\v sic et al. for the generator set $\{1,\dots,2t\}$. We further study circulant nut graphs with the generator set $\{1,\dots,2t+1\}\setminus\{t\}$, which yields nut graphs of every even order $n\geq 4t+4$ whenever $t$~is odd such that $t\not\equiv_{10}1$ and $t\not\equiv_{18}15$. This fully resolves Conjecture~9 from Ba\v sic et al.~[ibid.]. We also study the existence of $4t$-regular circulant nut graphs for small values of~$t$, which partially resolves Conjecture~10 of Ba\v sic et al.~[ibid.].

Chat View PDF

On circulant nut graphs

2021-01-01

Ivan Damnjanović , Dragan Stevanović

A nut graph is a simple graph whose adjacency matrix has the eigenvalue~0 with multiplicity~1 such that its corresponding eigenvector has no zero entries. Motivated by a question of Fowler … A nut graph is a simple graph whose adjacency matrix has the eigenvalue~0 with multiplicity~1 such that its corresponding eigenvector has no zero entries. Motivated by a question of Fowler et al.~[\emph{Disc. Math. Graph Theory} 40 (2020), 533--557] to determine the pairs $(n,d)$ for which a vertex-transitive nut graph of order $n$ and degree $d$ exists, Ba\v si\'c et al.\ [\arxiv{2102.04418}, 2021] initiated the study of circulant nut graphs. Here we first show that the generator set of a circulant nut graph necessarily contains equally many even and odd integers. Then we characterize circulant nut graphs with the generator set $\{x,x+1,\dots,x+2t-1\}$ for $x,t\in\N$, which generalizes the result of Ba\v si\'c et al.\ for the generator set $\{1,\dots,2t\}$. We further study circulant nut graphs with the generator set $\{1,\dots,2t+1\}\setminus\{t\}$, which yields nut graphs of every even order $n\geq 4t+4$ whenever $t$~is odd such that $t\not\equiv_{10}1$ and $t\not\equiv_{18}15$. This fully resolves Conjecture~9 from Ba\v si\'c et al.~[ibid.]. We also study the existence of $4t$-regular circulant nut graphs for small values of~$t$, which partially resolves Conjecture~10 of Ba\v si\'c et al.~[ibid.].

Chat View PDF

Finding counterexamples for a conjecture of Akbari, Alazemi and Andjelić

2021-01-01

Đorđe Stevanović , Ivan Damnjanović , Dragan Stevanović

For a graph $G$, its energy $\mathcal{E}(G)$ is the sum of absolute values of the eigenvalues of its adjacency matrix, the matching number $μ(G)$ is the number of edges in … For a graph $G$, its energy $\mathcal{E}(G)$ is the sum of absolute values of the eigenvalues of its adjacency matrix, the matching number $μ(G)$ is the number of edges in a maximum matching of $G$, while $Δ$ is the maximum vertex degree of $G$. Akbari, Alazemi and Anđelić in [Appl. Anal. Discrete Math. 15 (2021), 444--459] proved that $\mathcal{E}(G) \leq 2μ(G)$ when $G$ is connected and $Δ\geq6$, and conjectured that the same inequality is also valid when $2\leqΔ\leq5$. Here we first computationally enumerate small counterexamples for this conjecture and then provide two infinite families of counterexamples.

Chat View PDF

General approach to constructing optimal multipoint families of iterative methods using Hermite’s rational interpolation

2017-03-07

Jovana Džunić , Ivan Damnjanović

Gradient Polytope Faces Pursuit for large scale sparse recovery problems

2010-01-01

Aris Gretsistas , Ivan Damnjanović , Mark D. Plumbley

Polytope Faces Pursuit is a greedy algorithm that performs Basis Pursuit with similar order complexity to Orthogonal Matching Pursuit. The algorithm adds one basis vector at a time and adopts … Polytope Faces Pursuit is a greedy algorithm that performs Basis Pursuit with similar order complexity to Orthogonal Matching Pursuit. The algorithm adds one basis vector at a time and adopts a path-following approach based on the geometry of the polar polytope associated with the dual Linear Program. Its initial implementation uses the method of Cholesky factorization to update the solution vector at each step, which can be computationally expensive for solving large scale problems as it requires the succesive storage of large matrices. In this paper, we present a different approach using directional updates to estimate the solution vector at each time. The proposed method uses the gradient descent method, reducing the memory requirements and computational complexity. We demonstrate the application of this Gradient Polytope Faces Pursuit algorithm to a source separation problem.

Chat View PDF

Common Coauthors

Coauthor	Papers Together
Dragan Stevanović	16
Nino Bašić	8
Tomaž Pisanski	5
Arjana Žitnik	3
Đorđe Stevanović	3
Yaser Alizadeh	2
Kexiang Xu	2
Tomislav Došlić	2
Slobodan Filipovski	2
Patrick W. Fowler	1
Žarko Ranđelović	1
Mihailo Krstić	1
Milan Damnjanović	1
I. Milošević	1
Mark D. Plumbley	1
Jovana Džunić	1
Zarko Randjelovic	1
Hranislav Stanković	1
Ivan Stošić	1
Péter Csíkvári	1
Stephan Wagner	1
Salem Al-Yakoob	1
Aris Gretsistas	1
Marko V. Milošević	1

Commonly Cited References

On the construction of graphs of nullity one

1998-02-01

Irene Sciriha

On 12-regular nut graphs

2021-07-06

Nino Bašić , Martin Knor , Riste Škrekovski

A nut graph is a simple graph whose adjacency matrix is singular with 1-dimensional kernel such that the corresponding eigenvector has no zero entries. In 2020, Fowler et al. characterised … A nut graph is a simple graph whose adjacency matrix is singular with 1-dimensional kernel such that the corresponding eigenvector has no zero entries. In 2020, Fowler et al. characterised for each d ∈ {3, 4, …, 11} all values n such that there exists a d-regular nut graph of order n. In the present paper, we resolve the first open case d = 12, i.e. we show that there exists a 12-regular nut graph of order n if and only if n ≥ 16. We also present a result by which there are infinitely many circulant nut graphs of degree d ≡ 0 (mod 4) and no circulant nut graphs of degree d ≡ 2 (mod 4). The former result partially resolves a question by Fowler et al. on existence of vertex-transitive nut graphs of order n and degree d. We conclude the paper with problems, conjectures and ideas for further work.

Chat View PDF

Existence of regular nut graphs and the fowler construction

2020-10-30

Baptist Gauci , Tomaž Pisanski , Irene Sciriha

In this paper the problem of the existence of regular nut graphs is addressed. A generalization of Fowler?s Construction which is a local enlargement applied to a vertex in a … In this paper the problem of the existence of regular nut graphs is addressed. A generalization of Fowler?s Construction which is a local enlargement applied to a vertex in a graph is introduced to generate nut graphs of higher order. Let N (?) denote the set of integers n such that there exists a regular nut graph of degree ? and order n. It is proven that N (3) = {12} ? {2k : k ? 9} and that N (4) = {8, 10, 12} ? {n : n ? 14}. The problem of determining N (?) for ? > 4 remains completely open.

Chat View PDF

Existence of regular nut graphs for degree at most 11

2019-12-30

Patrick W. Fowler , John Baptist Gauci , Jan Goedgebeur +2 more

A nut graph is a singular graph with one-dimensional kernel and corresponding eigenvector with no zero elements.The problem of determining the orders n for which d-regular nut graphs exist was … A nut graph is a singular graph with one-dimensional kernel and corresponding eigenvector with no zero elements.The problem of determining the orders n for which d-regular nut graphs exist was recently posed by Gauci, Pisanski and Sciriha.These orders are known for d ≤ 4.Here we solve the problem for all remaining cases d ≤ 11 and determine the complete lists of all d-regular nut graphs of order n for small values of d and n.The existence or non-existence of small regular nut graphs is determined by a computer search.The main tool is a construction that produces, for any d-regular nut graph of order n, another d-regular nut graph of order n+2d.If we are given a sufficient number of d-regular nut graphs of consecutive orders, called seed graphs, this construction may be applied in such a way that the existence of all d-regular nut graphs of higher orders is established.For even d the orders n are indeed consecutive, while for odd d the orders n are consecutive even numbers.Furthermore, necessary conditions for combinations of order and degree for vertex-transitive nut graphs are derived.

Chat View PDF

Coalesced and embedded nut graphs in singular graphs

2008-06-19

Irene Sciriha

A nut graph has a non-invertible (singular) 0-1 adjacency matrix with non-zero entries in every kernel eigenvector. We investigate how the concept of nut graphs emerges as an underlying theme … A nut graph has a non-invertible (singular) 0-1 adjacency matrix with non-zero entries in every kernel eigenvector. We investigate how the concept of nut graphs emerges as an underlying theme in the theory of singular graphs. It is known that minimal configurations (MCs) are necessarily found as subgraphs of singular graphs. We construct MCs having nut graphs as subgraphs. Nut graphs can be coalesced with singular graphs at particular vertices or grown into a family of core graphs of larger nullity by adding a vertex at a time. Moreover, we propose a construction of nut line graph of trees by coalescence and a local enlargement of nut fullerenes and tetravalent nut graphs.

Chat View PDF

On circulant nut graphs

2021-10-18

Ivan Damnjanović , Dragan Stevanović

A characterization of singular graphs

2007-01-01

Irene Sciriha

Characterization of singular graphs can be reduced to the non-trivial solutions ofa system of linear homogeneous equations Ax = 0 for the 0-1 adjacency matrix A. A graph G issingular … Characterization of singular graphs can be reduced to the non-trivial solutions ofa system of linear homogeneous equations Ax = 0 for the 0-1 adjacency matrix A. A graph G issingular of nullity η(G) ≥ 1, if the dimension of the nullspace ker(A) of its adjacency matrix Ais η(G). Necessary and sufficient conditions are determined for a graph to be singular in terms ofadmissible induced subgraphs

Functions on adjacent vertex degrees of trees with given degree sequence

2014-06-28

Hua Wang

Abstract In this note we consider a discrete symmetric function f(x, y) where $$f(x,a) + f(y,b) \geqslant f(y,a) + f(x,b) for any x \geqslant y and a \geqslant b,$$ associated … Abstract In this note we consider a discrete symmetric function f(x, y) where $$f(x,a) + f(y,b) \geqslant f(y,a) + f(x,b) for any x \geqslant y and a \geqslant b,$$ associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as $$\sum\limits_{uv \in E(T)} {f(deg(u),deg(v))} ,$$ are characterized by the “greedy tree” and “alternating greedy tree”. This is achieved through simple generalizations of previously used ideas on similar questions. As special cases, the already known extremal structures of the Randic index follow as corollaries. The extremal structures for the relatively new sum-connectivity index and harmonic index also follow immediately, some of these extremal structures have not been identified in previous studies.

Chat View PDF

Two families of circulant nut graphs

2023-01-01

Ivan Damnjanović

Chat View PDF

Charting the space of chemical nut graphs

2020-01-01

Patrick W. Fowler , Tomaž Pisanski , Nino Bašić

Molecular graphs of unsaturated carbon frameworks or hydrocarbons pruned of hydrogen atoms, are chemical graphs. A chemical graph is a connected simple graph of maximum degree $3$ or less. A … Molecular graphs of unsaturated carbon frameworks or hydrocarbons pruned of hydrogen atoms, are chemical graphs. A chemical graph is a connected simple graph of maximum degree $3$ or less. A nut graph is a connected simple graph with a singular adjacency matrix that has one zero eigenvalue and a non-trivial kernel eigenvector without zero entries. Nut graphs have no vertices of degree $1$: they are leafless. The intersection of these two sets, the chemical nut graphs, is of interest in applications in chemistry and molecular physics, corresponding to structures with fully distributed radical reactivity and omniconducting behaviour at the Fermi level. A chemical nut graph consists of $v_2 \ge 0$ vertices of degree $2$ and an even number, $v_3 > 0$, of vertices of degree $3$. With the aid of systematic local constructions that produce larger nut graphs from smaller, the combinations $(v_3, v_2)$ corresponding to realisable chemical nut graphs are characterised. Apart from a finite set of small cases, and two simply defined infinite series, all combinations $(v_3, v_2 )$ with even values of $v_3 > 0$ are realisable as chemical nut graphs. Of these combinations, only $(20,0)$ cannot be realised by a planar chemical nut graph. The main result characterises the ranges of edge counts for chemical nut graphs of all orders $n$.

Chat View PDF

Toeplitz and Circulant Matrices: A Review

2005-01-01

Robert M. Gray

Toeplitz and Circulant Matrices: A review derives in a tutorial manner the fundamental theorems on the asymptotic behavior of eigenvalues, inverses, and products of banded Toeplitz matrices and Toeplitz matrices … Toeplitz and Circulant Matrices: A review derives in a tutorial manner the fundamental theorems on the asymptotic behavior of eigenvalues, inverses, and products of banded Toeplitz matrices and Toeplitz matrices with absolutely summable elements. Mathematical elegance and generality are sacrificed for conceptual simplicity and insight in the hope of making these results available to engineers lacking either the background or endurance to attack the mathematical literature on the subject. By limiting the generality of the matrices considered, the essential ideas and results can be conveyed in a more intuitive manner without the mathematical machinery required for the most general cases. As an application the results are applied to the study of the covariance matrices and their factors of linear models of discrete time random processes. Toeplitz and Circulant Matrices: A review is written for students and practicing engineers in an accessible manner bringing this important topic to a wider audience.

Chat View PDF

Complete resolution of the circulant nut graph order–degree existence problem

2023-10-23

Ivan Damnjanović

Chat View PDF

A classification of cubic bicirculants

2006-09-15

Tomaž Pisanski

Generation and properties of nut graphs

2017-01-01

Kris Coolsaet , Patrick W. Fowler , Jan Goedgebeur

A nut graph is a graph on at least 2 vertices whose adjacency matrix has nullity 1 and for which non-trivial kernel vectors do not contain a zero. Chemical graphs … A nut graph is a graph on at least 2 vertices whose adjacency matrix has nullity 1 and for which non-trivial kernel vectors do not contain a zero. Chemical graphs are connected, with maximum degree at most three. We present a new algorithm for the exhaustive generation of non-isomorphic nut graphs. Using this algorithm, we determined all nut graphs up to 13 vertices and all chemical nut graphs up to 22 vertices. Furthermore, we determined all nut graphs among the cubic polyhedra up to 34 vertices and all nut fullerenes up to 250 vertices. Nut graphs are of interest in chemistry of conjugated systems, in models of electronic structure, radical reactivity and molecular conduction. The relevant mathematical properties of chemical nut graphs are the position of the zero eigenvalue in the graph spectrum, and the dispersion in magnitudes of kernel eigenvector entries ($r$: the ratio of maximum to minimum magnitude of entries). Statistics are gathered on these properties for all the nut graphs generated here. We also show that all chemical nut graphs have $r \ge 2$ and that there is at least one chemical nut graph with $r = 2$ for every order $n \ge 9$ (with the exception of $n = 10$).

Chat View PDF

Classification of cubic vertex-transitive tricirculants

2020-05-29

Primož Potočnik , Micael Toledo

A finite graph is called a tricirculant if admits a cyclic group of automorphism which has precisely three orbits on the vertex-set of the graph, all of equal size. We … A finite graph is called a tricirculant if admits a cyclic group of automorphism which has precisely three orbits on the vertex-set of the graph, all of equal size. We classify all finite connected cubic vertex-transitive tricirculants. We show that except for some small exceptions of order less than 54 , each of these graphs is either a prism of order 6 k with k odd, a Möbius ladder, or it falls into one of two infinite families, each family containing one graph for every order of the form 6 k with k odd.

Chat View PDF

Trees with Maximum Vertex-Degree-Based Topological Indices

2022-04-01

Wei Gao

Let G be a graph with vertex set V (G) = {v 1 , v 2 , . . ., v n } and edge set E(G), and d(v i … Let G be a graph with vertex set V (G) = {v 1 , v 2 , . . ., v n } and edge set E(G), and d(v i ) be the degree of the vertex v i .The definition of a vertex-degree-based topological index of G is as followswhere f (x, y) > 0 is a symmetric real function with x > 0 and y > 0.In this paper, we find the extremal trees with the maximum vertex-degree-based topological index T f among all trees of order n when f (x, y) is increasing and concave up in respect to variable x (to variable y too, of course).

Chat View PDF

New transmission irregular chemical graphs

2023-08-05

Kexiang Xu , Jing Tian , Sandi Klavžar

Chat View PDF

A Note on Extremal Sombor Indices of Trees with a Given Degree Sequence

2023-01-01

Ivan Damjanović , Marko V. Milošević , Dragan Stevanović

Chat View PDF

Extremal problems on Sombor indices of unicyclic graphs with a given diameter

2022-04-13

Hechao Liu

Chat View PDF

On the Graphs with Minimum Sombor Index

2022-04-01

Aarman Aashtab , Saieed Akbari , Saba Madadinia +2 more

For a graph G the Sombor index of G is defined as uv∈E(G) d(u) 2 + d(v) 2 , where d(u) is the degree of u in G.In the current … For a graph G the Sombor index of G is defined as uv∈E(G) d(u) 2 + d(v) 2 , where d(u) is the degree of u in G.In the current paper, we study the structure of a graph with minimum Sombor index among all graphs with fixed order and fixed size.It is shown that in every graph with minimum Sombor index the difference between minimum and maximum degrees is at most 1.

Sombor index and degree-related properties of simplicial networks

2021-12-28

Yilun Shang

Chat View PDF

Sombor index: review of extremal results and bounds

2022-03-19

Hechao Liu , Iván Gutman , Lihua You +1 more

Vertex-degree-based topological indices of oriented trees

2022-07-16

Sergio Bermudo , Roberto Cruz , Juan Rada

On Sombor index of trees with fixed domination number

2022-01-25

Xiaoling Sun , Jianwei Du

Properties of almost all graphs and complexes

1979-09-01

Andreas Blass , Frank Harary

Abstract There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will … Abstract There are many results in the literature asserting that almost all or almost no graphs have some property. Our object is to develop a general logical theorem that will imply almost all of these results as corollaries. To this end, we propose the first‐order theory of almost all graphs by presenting Axiom n which states that for each sequence of 2n distinct vertices in a graph ( u 1 , …, u n , v 1 , …, v n ), there exists another vertex w adjacent to each u 1 and not adjacent to any v i . A simple counting argument proves that for each n , almost all graphs satisfy Axiom n . It is then shown that any sentence that can be stated in terms of these axioms is true in almost all graphs or in almost none. This has several immediate consequences, most of which have already been proved separately including: (1) For any graph H , almost all graphs have an induced subgraph isomorphic to H . (2) Almost no graphs are planar, or chordal, or line graphs. (3) Almost all grpahs are connected wiht diameter 2. It is also pointed out that these considerations extend to digraphs and to simplicial complexes.

Characterization of molecular branching

1975-11-01

Milan Randić

ADVERTISEMENT RETURN TO ISSUEPREVArticleNEXTCharacterization of molecular branchingMilan RandicCite this: J. Am. Chem. Soc. 1975, 97, 23, 6609–6615Publication Date (Print):November 1, 1975Publication History Published online1 May 2002Published inissue 1 November 1975https://pubs.acs.org/doi/10.1021/ja00856a001https://doi.org/10.1021/ja00856a001research-articleACS … ADVERTISEMENT RETURN TO ISSUEPREVArticleNEXTCharacterization of molecular branchingMilan RandicCite this: J. Am. Chem. Soc. 1975, 97, 23, 6609–6615Publication Date (Print):November 1, 1975Publication History Published online1 May 2002Published inissue 1 November 1975https://pubs.acs.org/doi/10.1021/ja00856a001https://doi.org/10.1021/ja00856a001research-articleACS PublicationsRequest reuse permissionsArticle Views2766Altmetric-Citations2514LEARN ABOUT THESE METRICSArticle Views are the COUNTER-compliant sum of full text article downloads since November 2008 (both PDF and HTML) across all institutions and individuals. These metrics are regularly updated to reflect usage leading up to the last few days.Citations are the number of other articles citing this article, calculated by Crossref and updated daily. Find more information about Crossref citation counts.The Altmetric Attention Score is a quantitative measure of the attention that a research article has received online. Clicking on the donut icon will load a page at altmetric.com with additional details about the score and the social media presence for the given article. Find more information on the Altmetric Attention Score and how the score is calculated. Share Add toView InAdd Full Text with ReferenceAdd Description ExportRISCitationCitation and abstractCitation and referencesMore Options Share onFacebookTwitterWechatLinked InRedditEmail Other access optionsGet e-Alertsclose Get e-Alerts

Classification of Cubic Symmetric Tricirculants

2012-05-31

István Kovács , Klavdija Kutnar , Dragan Marušič +1 more

A tricirculant is a graph admitting a non-identity automorphism having three cycles of equal length in its cycle decomposition. A graph is said to be symmetric if its automorphism group … A tricirculant is a graph admitting a non-identity automorphism having three cycles of equal length in its cycle decomposition. A graph is said to be symmetric if its automorphism group acts transitively on the set of its arcs. In this paper it is shown that the complete bipartite graph $K_{3,3}$, the Pappus graph, Tutte's 8-cage and the unique cubic symmetric graph of order 54 are the only connected cubic symmetric tricirculants.

Chat View PDF

On the nullities of quartic circulant graphs and their extremal null spaces

2022-01-01

Ivan Damnjanović

Chat View PDF

General properties on Sombor indices

2021-05-06

Juan Rada , José M. Rodrı́guez , José M. Sigarreta

The expected values and variances for Sombor indices in a general random chain

2021-07-27

Weilin Zhang , Lihua You , Hechao Liu +1 more

Sombor index of chemical graphs

2021-02-02

Roberto Cruz , Iván Gutman , Juan Rada

Approximate formulas for some functions of prime numbers

1962-03-01

J. Barkley Rosser , Lowell Schoenfeld

Extremal values of the Sombor index in unicyclic and bicyclic graphs

2021-03-06

Roberto Cruz , Juan Rada

On the distance spectral radius of trees with given degree sequence

2019-12-20

Kennteth Dadedzi , Valisoa Razanajatovo Misanantenaina , Stephan Wagner

We consider the problem of maximizing the distance spectral radius and a slight generalization thereof among all trees with some prescribed degree sequence.We prove in particular that the maximum of … We consider the problem of maximizing the distance spectral radius and a slight generalization thereof among all trees with some prescribed degree sequence.We prove in particular that the maximum of the distance spectral radius has to be attained by a caterpillar for any given degree sequence.The same holds true for the terminal distance matrix.Moreover, we consider a generalized version of the reverse distance matrix and also study its spectral radius for trees with given degree sequence.We prove that the spectral radius is always maximized by a greedy tree.This implies several corollaries, among them a "reversed" version of a conjecture of Stevanović and Ilić.Our results parallel similar theorems for the Wiener index and other invariants.

Infinite family of 2-connected transmission irregular graphs

2018-09-03

Andrey A. Dobrynin

A census of small transitive groups and vertex-transitive graphs

2019-06-27

Derek F. Holt , Gordon Royle

Chat View PDF

Spectral moments of trees with given degree sequence

2013-10-30

Eric Ould Dadah Andriantiana , Stephan Wagner

Chat View PDF

Generation and properties of nut graphs

2018-01-01

Kris Coolsaet , Patrick W. Fowler , Jan Goedgebeur

A nut graph is a graph on at least 2 vertices whose adjacency matrix has nullity 1 and for which non-trivial kernel vectors do not contain a zero. Chemical graphs … A nut graph is a graph on at least 2 vertices whose adjacency matrix has nullity 1 and for which non-trivial kernel vectors do not contain a zero. Chemical graphs are connected, with maximum degree at most three. We present a new algorithm for the exhaustive generation of non-isomorphic nut graphs. Using this algorithm, we determined all nut graphs up to 13 vertices and all chemical nut graphs up to 22 vertices. Furthermore, we determined all nut graphs among the cubic polyhedra up to 34 vertices and all nut fullerenes up to 250 vertices. Nut graphs are of interest in chemistry of conjugated systems, in models of electronic structure, radical reactivity and molecular conduction. The relevant mathematical properties of chemical nut graphs are the position of the zero eigenvalue in the graph spectrum, and the dispersion in magnitudes of kernel eigenvector entries (r: the ratio of maximum to minimum magnitude of entries). Statistics are gathered on these properties for all the nut graphs generated here. We also show that all chemical nut graphs have r = 2 and that there is at least one chemical nut graph with r ≥ 2 for every order n ≥ 9 (with the exception of n = 10).

Chat View PDF

Greedy Trees, Subtrees and Antichains

2013-08-30

Eric Ould Dadah Andriantiana , Stephan Wagner , Hua Wang

Greedy trees are constructed from a given degree sequence by a simple greedy algorithm that assigns the highest degree to the root, the second-, third-, ... highest degrees to the … Greedy trees are constructed from a given degree sequence by a simple greedy algorithm that assigns the highest degree to the root, the second-, third-, ... highest degrees to the root's neighbors, and so on. They have been shown to maximize or minimize a number of different graph invariants among trees with a given degree sequence. In particular, the total number of subtrees of a tree is maximized by the greedy tree. In this work, we show that in fact a much stronger statement holds true: greedy trees maximize the number of subtrees of any given order. This parallels recent results on distance-based graph invariants. We obtain a number of corollaries from this fact and also prove analogous results for related invariants, most notably the number of antichains of given cardinality in a rooted tree.

Chat View PDF

On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs

2018-02-09

Yaser Alizadeh , Sandi Klavžar

Eccentricity sums in trees

2016-03-11

Heather C. Smith , László Á. Székely , Hua Wang

Chat View PDF

Extremal Trees with Fixed Degree Sequence

2021-01-14

Eric Ould Dadah Andriantiana , Valisoa Razanajatovo Misanantenaina , Stephan Wagner

The greedy tree $\mathcal{G}(D)$ and the $\mathcal{M}$-tree $\mathcal{M}(D)$ are known to be extremal among trees with degree sequence $D$ with respect to various graph invariants. This paper provides a general … The greedy tree $\mathcal{G}(D)$ and the $\mathcal{M}$-tree $\mathcal{M}(D)$ are known to be extremal among trees with degree sequence $D$ with respect to various graph invariants. This paper provides a general theorem that covers a large family of invariants for which $\mathcal{G}(D)$ or $\mathcal{M}(D)$ is extremal. Many known results, for example on the Wiener index, the number of subtrees, the number of independent subsets and the number of matchings follow as corollaries, as do some new results on invariants such as the number of rooted spanning forests, the incidence energy and the solvability. We also extend our results on trees with fixed degree sequence $D$ to the set of trees whose degree sequence is majorised by a given sequence $D$, which also has a number of applications.

Chat View PDF

Practical graph isomorphism, II

2013-09-27

Brendan D. McKay , Adolfo Piperno

Chat View PDF

On interval transmission irregular graphs

2021-03-01

Salem Al-Yakoob , Dragan Stevanović

Chat View PDF

Cyclotomic Polynomials

2017-10-27

Kevin Broughan

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content. A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Sombor index of trees with at most three branch vertices

2021-06-13

Roberto Cruz , Juan Rada , José M. Sigarreta

On the extremal Sombor index of trees with a given diameter

2021-10-28

Shuchao Li , Zheng Wang , Minjie Zhang

Root-finding by fitting rational functions

1980-01-01

F. M. Larkin

A tabular, recursive method is presented for the computation of a sequence of abscissae designed to converge to a simple zero of an analytic function. The key to the method … A tabular, recursive method is presented for the computation of a sequence of abscissae designed to converge to a simple zero of an analytic function. The key to the method is an efficient means for evaluating the zeros of a sequence of rational functions, having linear numerators, fitted to information previously computed. Regional and asymptotic convergence properties of the method are described. Conditions sufficient to ensure convergence are derived, and it is shown that asymptotically quadratic convergence can be achieved, at the cost of only a moderate amount of "overhead" computation.

Chat View PDF

Girth and Euclidean distortion

2002-06-01

Nathan Linial , Avner Magen , Assaf Naor

The spectra of the adjacency matrix and Laplacian matrix for some balanced trees

2005-03-03

Óscar Rojo , Ricardo L. Soto