Nino Bašić

Search for another author

Author Description

Ask a Question About This Mathematician

All published works (38)

On cubic polycirculant nut graphs

2025-05-06

Nino Bašić , Ivan Damnjanović

Nut graphs with a given automorphism group

2025-02-18

Nino Bašić , Patrick W. Fowler

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

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

On regular graphs with Šoltés vertices

2024-06-05

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

Let W(G) be the Wiener index of a graph G. We say that a vertex v ∈ V(G) is a Šoltés vertex in G if W(G − v) = W(G), … Let W(G) be the Wiener index of a graph G. We say that a vertex v ∈ V(G) is a Šoltés vertex in G if W(G − v) = W(G), i.e. the Wiener index does not change if the vertex v is removed. In 1991, Šoltés posed the problem of identifying all connected graphs G with the property that all vertices of G are Šoltés vertices. The only such graph known to this day is C11. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least k Šoltes vertices; or one may look for α-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least α. Note that the original problem is, in fact, to find all 1-Šoltés graphs. We intuitively believe that every 1-Šoltés graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more Šoltés vertices. In this paper, we present several partial results. For every r ≥ 1 we describe a construction of an infinite family of cubic 2-connected graphs with at least 2r Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any 1-Šoltés graph. We are only able to provide examples of large ⅓-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no 1-Šoltés graph other than C11 exists.

Chat View PDF

Vertex and Edge Orbits in Nut Graphs

2024-05-31

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

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. If the isolated … 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. If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they are connected, non-bipartite, and have no leaves. It is shown that a nut graph $G$ always has at least one more edge orbit than it has vertex orbits: $o_e(G) \geq o_v(G) + 1$, with the obvious corollary that edge-transitive nut graphs do not exist. We give infinite familes of vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs with two orbits of vertices and three of edges. Several constructions for nut graphs from smaller starting graphs are known: double subdivision of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with preservation of the degree sequence. To these we add multiplier constructions that yield nut graphs from regular (not necessarily nut graph) parents. In general, constructions can have different effects on automorphism group and counts of vertex and edge orbits, but in the case where the automorphism group is ‘preserved’, they can be used in a predictable way to control vertex and edge orbit numbers.

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

Nut graphs with a given automorphism group

2024-05-07

Nino Bašić , Patrick W. Fowler

A nut graph is a simple graph of order 2 or more for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no … A nut graph is a simple graph of order 2 or more for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no zero entry (i.e. are full). It is shown by construction that every finite group can be represented as the group of automorphisms of infinitely many nut graphs. It is further shown that such nut graphs exist even within the class of regular graphs; the cases where the degree is 8, 12, 16, 20 or 24 are realised explicitly.

Chat View PDF

Solving the Mostar index inverse problem

2024-02-28

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

On regular graphs with Šoltés vertices

2023-01-01

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

Let $W(G)$ be the Wiener index of a graph $G$. We say that a vertex $v \in V(G)$ is a \v{S}olt\'es vertex in $G$ if $W(G - v) = W(G)$, … Let $W(G)$ be the Wiener index of a graph $G$. We say that a vertex $v \in V(G)$ is a \v{S}olt\'es vertex in $G$ if $W(G - v) = W(G)$, i.e. the Wiener index does not change if the vertex $v$ is removed. In 1991, \v{S}olt\'es posed the problem of identifying all connected graphs $G$ with the property that all vertices of $G$ are \v{S}olt\'es vertices. The only such graph known to this day is $C_{11}$. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least $k$ \v{S}oltes vertices; or one may look for $\alpha$-\v{S}olt\'es graphs, i.e. graphs where the ratio between the number of \v{S}olt\'es vertices and the order of the graph is at least $\alpha$. Note that the original problem is, in fact, to find all $1$-\v{S}olt\'es graphs. We intuitively believe that every $1$-\v{S}olt\'es graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more \v{S}olt\'es vertices. In this paper, we present several partial results. We describe a construction that gives rise to an infinite family of cubic $2$-connected graphs with two \v{S}olt\'es vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any $1$-\v{S}olt\'es graph. We are only able to provide examples of large $\frac{1}{3}$-\v{S}olt\'es graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no $1$-\v{S}olt\'es graph other than $C_{11}$ exists.

Chat View PDF

Vertex and edge orbits in nut graphs

2023-01-01

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

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. If the isolated … 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. If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they are connected, non-bipartite, and have no leaves. It is shown that a nut graph $G$ always has at least one more edge orbit than it has vertex orbits: $o_e(G) \geq o_v(G) + 1$, with the obvious corollary that edge transitive nut graphs do not exist. We give infinite familes of vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs with two orbits of vertices and three of edges. Several constructions for nut graphs from smaller starting graphs are known: double subdivision of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with preservation of the degree sequence. To these we add multiplier constructions that yield nut graphs from regular (not necessarily nut graph) parents. In general, constructions can have different effects on automorphism group and counts of vertex and edge orbits, but in the case where the automorphism group is `preserved', they can be used in a predictable way to control vertex and edge orbit numbers.

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

A Curious Family of Convex Benzenoids and Their Altans

2022-05-19

Nino Bašić , Patrick W. Fowler

The altan graph of G, a(G, H), is constructed from graph G by choosing an attachment set H from the vertices of G and attaching vertices of H to alternate … The altan graph of G, a(G, H), is constructed from graph G by choosing an attachment set H from the vertices of G and attaching vertices of H to alternate vertices of a new perimeter cycle of length 2|H|.When G is a polycyclic plane graph with maximum degree 3, the natural choice for the attachment set is to take all perimeter degree-2 vertices in the order encountered in a walk around the perimeter.The construction has implications for the electronic structure and chemistry of carbon nanostructures with molecular graph a(G, H), as kernel eigenvectors of the altan correspond to non-bonding π molecular orbitals of the corresponding unsaturated hydrocarbon.Benzenoids form an important subclass of carbon nanostructures.A convex benzenoid has a boundary on which all vertices of degree 3 have exactly two neighbours of degree 2. The nullity of a graph is the dimension of the kernel of its adjacency matrix.The possible values for the excess nullity of a(G, H) over that of G are 2, 1, or 0.Moreover, altans of benzenoids have nullity at least 1.Examples of benzenoids where the excess nullity is 2 were found recently.It has been conjectured that the excess nullity when G is a convex benzenoid is at most 1.Here, we exhibit an infinite family of convex benzenoids with 3-fold dihedral symmetry (point group D 3h ) where nullity increases from 2 to 3 under altanisation.This family accounts for all known examples with the excess nullity of 1 where the parent graph is a singular convex benzenoid.

On the Nullity of Altans and Iterated Altans

2022-04-01

Nino Bašić , Patrick W. Fowler

Altanisation (formation of the altan of a parent structure) originated in the chemical literature as a formal device for constructing generalised coronenes from smaller structures.The altan of graph G, denoted … Altanisation (formation of the altan of a parent structure) originated in the chemical literature as a formal device for constructing generalised coronenes from smaller structures.The altan of graph G, denoted a(G, H), depends on the choice of attachment set H (a cyclic h-tuple of vertices of G).From a given pair (G, H), the altan construction produces a pair (G ′ , H ′ ), where H ′ is called the induced attachment set.Repetition of the construction, using at each stage the attachment set induced in the previous step, defines the iterated altan.Here, we prove sharp bounds for the nullity of altan and iterated altan graphs based on a general parent graph: for any attachment set with odd h, nullities of altan and parent are equal; for any h and all k 1, the k-th altan has the same nullity as the first; for any attachment set with even h, the nullity of the altan exceeds the nullity of the parent graph by one of the three values {0, 1, 2}.The case of excess nullity 2 has not been noticed before; for benzenoids with the natural attachment set consisting of the CH sites, it occurs first for a parent structure with 5 hexagons.On the basis of extensive computation, it is conjectured that in fact no altan of a convex benzenoid has excess nullity 2.

Chat View PDF

On the Nullity of Altans and Iterated Altans

2022-01-01

Nino Bašić , Patrick W. Fowler

Altanisation (formation of the altan of a parent structure) originated in the chemical literature as a formal device for constructing generalised coronenes from smaller structures. The altan of graph $G$, … Altanisation (formation of the altan of a parent structure) originated in the chemical literature as a formal device for constructing generalised coronenes from smaller structures. The altan of graph $G$, denoted $\mathfrak{a}(G, H)$, depends on the choice of attachment set $H$ (a cyclic $h$-tuple of vertices of $G$). From a given pair $(G, H)$, the altan construction produces a pair $(G', H')$, where $H'$ is called the induced attachment set. Repetition of the construction, using at each stage the attachment set induced in the previous step, defines the iterated altan. Here, we prove sharp bounds for the nullity of altan and iterated altan graphs based on a general parent graph: for any attachment set with odd $h$, nullities of altan and parent are equal; for any $h$ and all $k \geq 1$, the $k$-th altan has the same nullity as the first; for any attachment set with even $h$, the nullity of the altan exceeds the nullity of the parent graph by one of the three values $\{0, 1, 2\}$. The case of excess nullity $2$ has not been noticed before; for benzenoids with the natural attachment set consisting of the CH sites, it occurs first for a parent structure with $5$ hexagons. On the basis of extensive computation, it is conjectured that in fact no altan of a convex benzenoid has excess nullity $2$.

Chat View PDF

Point-ellipse configurations and related topics

2021-07-26

Gábor Gévay , Nino Bašić , Jurij Kovič +1 more

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

Catacondensed Chemical Hexagonal Complexes: A Natural Generalisation of Benzenoids

2021-04-02

Cate S. Anstöter , Nino Bašić , Patrick W. Fowler +1 more

Catacondensed benzenoids (those benzenoids having no carbon atom belonging to three hexagonal rings) form the simplest class of polycyclic aromatic hydrocarbons (PAH). They have a long history of study and … Catacondensed benzenoids (those benzenoids having no carbon atom belonging to three hexagonal rings) form the simplest class of polycyclic aromatic hydrocarbons (PAH). They have a long history of study and are of wide chemical importance. In this paper, mathematical possibilities for natural extension of the notion of a catacondensed benzenoid are discussed, leading under plausible chemically and physically motivated restrictions to the notion of a catacondensed chemical hexagonal complex (CCHC). A general polygonal complex is a topological structure composed of polygons that are glued together along certain edges. A polygonal complex is flat if none of its edges belong to more than two polygons. A connected flat polygonal complex determines an orientable or nonorientable surface, possibly with boundary. A CCHC is then a connected flat polygonal complex all of whose polygons are hexagons and each of whose vertices belongs to at most two hexagonal faces. We prove that all CCHC are Kekulean and give formulas for counting the perfect matchings in a series of examples based on expansion of cubic graphs in which the edges are replaced by linear polyacenes of equal length. As a preliminary assessment of the likely stability of molecules with CCHC structure, all-electron quantum chemical calculations are applied to molecular structures based on several CCHC, using either linear or kinked unbranched catafused polyacenes as the expansion motif. The systems examined all have closed shells according to Huckel theory and all correspond to minima on the potential surface, thus passing the most basic test for plausibility as a chemical species.

On $12$-regular nut graphs

2021-02-08

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 \in \{3,4,\ldots,11\}$ all values $n$ such that there exists a $d$-regular nut graph of order $n$. In the present paper, we determine all values $n$ for which a $12$-regular nut graph of order $n$ exists. We also present a result by which there are infinitely many circulant nut graphs of degree $d \equiv 0 \pmod 4$ and no circulant nut graph of degree $d \equiv 2 \pmod 4$.

Chat View PDF

On singular signed graphs with nullspace spanned by a full vector: signed nut graphs

2021-01-01

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

A signed graph has edge weights drawn from the set $\{+1,-1\}$, and is termed sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise … A signed graph has edge weights drawn from the set $\{+1,-1\}$, and is termed sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is called sign-unbalanced. A nut graph has a one dimensional kernel with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which unsigned regular nut graphs exist were determined recently for the degrees up to $11$. By extending the definition to signed nut graphs, we find all pairs $(\rho, n)$ for which a $\rho$-regular nut graph (sign-balanced or sign-unbalanced) of order $n$ exists with $\rho \le 11$. We devise a construction for signed nut graphs based on a smaller `seed' graph, giving infinite series of both sign-balanced and sign-unbalanced $\rho$-regular nut graphs. All orders for which a complete sign-unbalanced nut graph exists are characterised; they have underlying graph $K_n$ with $n \equiv 1 \pmod 4$. All orders for which a regular sign-unbalanced nut graph with $\rho = n - 2$ exists are also characterised; they have an underlying cocktail-party graph $\mathrm{CP}(n)$ with even $n \geq 8$.

Chat View PDF

Catacondensed Chemical Hexagonal Complexes: A Natural Generalisation of Benzenoids

2021-01-01

Cate S. Anstöter , Nino Bašić , Patrick W. Fowler +1 more

Catacondensed benzenoids (those benzenoids having no carbon atom belonging to three hexagonal rings) form the simplest class of polycyclic aromatic hydrocarbons (PAH). They have a long history of study and … Catacondensed benzenoids (those benzenoids having no carbon atom belonging to three hexagonal rings) form the simplest class of polycyclic aromatic hydrocarbons (PAH). They have a long history of study and are of wide chemical importance. In this paper, mathematical possibilities for natural extension of the notion of a catacondensed benzenoid are discussed, leading under plausible chemically and physically motivated restrictions to the notion of a catacondensed chemical hexagonal complex (CCHC). A general polygonal complex is a topological structure composed of polygons that are glued together along certain edges. A polygonal complex is flat if none of its edges belong to more than two polygons. A connected flat polygonal complex determines an orientable or nonorientable surface, possibly with boundary. A CCHC is then a connected flat polygonal complex all of whose polygons are hexagons and each of whose vertices belongs to at most two hexagonal faces. We prove that all CCHC are Kekulean and give formulas for counting the perfect matchings in a series of examples based on expansion of cubic graphs in which the edges are replaced by linear polyacenes of equal length. As a preliminary assessment of the likely stability of molecules with CCHC structure, all-electron quantum chemical calculations are applied to molecular structures based on several CCHC, using either linear or kinked unbranched catafused polyacenes as the expansion motif. The systems examined all have closed shells according to H\"uckel theory and all correspond to minima on the potential surface, thus passing the most basic test for plausibility as a chemical species.

Chat View PDF

On $12$-regular nut graphs

2021-01-01

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

Chat View PDF

Signed nut graphs

2020-09-18

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

Orders for which regular nut graphs exist have been determined recently for the degrees up to $11$. In this paper we extend the notion of nut graphs to signed graphs, … Orders for which regular nut graphs exist have been determined recently for the degrees up to $11$. In this paper we extend the notion of nut graphs to signed graphs, i.e. graphs with edges weighted either by $+1$ or $-1$. A signed graph is sign-balanced if it is equivalent to an unsigned graph under an intuitive operation of sign switching, otherwise it is sign-unbalanced. By including signed nut graphs, we find all pairs $(\rho, n)$ for which a $\rho$-regular nut graph of order $n$ exists with $\rho \le 11$. In addition, we show how a literature construction for obtaining larger nut graphs can be extended to signed graphs, giving a construction for both sign-balanced and sign-unbalanced $\rho$-regular signed nut graphs.

Chat View PDF

On singular signed graphs with nullspace spanned by a full vector: Signed nut graphs.

2020-09-18

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

Chat View PDF

Convexity Deficit of Benzenoids

2020-01-01

Nino Bašić , Patrick W. Fowler , Sara Sabrina Zemljič +6 more

In 2012, a family of benzenoids was introduced by Cruz, Gutman, and Rada, which they called convex benzenoids. In this paper we introduce the convexity deficit, a new topological index … In 2012, a family of benzenoids was introduced by Cruz, Gutman, and Rada, which they called convex benzenoids. In this paper we introduce the convexity deficit, a new topological index intended for benzenoids and, more generally, fusenes. This index measures by how much a given fusene departs from convexity. It is defined in terms of the boundary-edges code. In particular, convex benzenoids are exactly the benzenoids having convexity deficit equal to 0. Quasi-convex benzenoids form the family of non-convex benzenoids that are closest to convex, i.e., they have convexity deficit equal to 1. Finally, we investigate convexity deficit of several important families of benzenoids.

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

Catacondensed Chemical Hexagonal Complexes: A Natural Generalisation of Benzenoids

2020-01-01

Cate S. Anstöter , Nino Bašić , Patrick W. Fowler +1 more

Catacondensed benzenoids (those benzenoids having no carbon atom belonging to three hexagonal rings) form the simplest class of polycyclic aromatic hydrocarbons (PAH).They have a long history of study and are … Catacondensed benzenoids (those benzenoids having no carbon atom belonging to three hexagonal rings) form the simplest class of polycyclic aromatic hydrocarbons (PAH).They have a long history of study and are of wide chemical importance.In this paper, mathematical possibilities for natural extension of the notion of a catacondensed benzenoid are discussed, leading under plausible chemically and physically motivated restrictions to the notion of a catacondensed chemical hexagonal complex (CCHC).A general polygonal complex is a topological structure composed of polygons that are glued together along certain edges.A polygonal complex is flat if none of its edges belong to more than two polygons.A connected flat polygonal complex determines an orientable or nonorientable surface, possibly with boundary.A CCHC is then a connected flat polygonal complex all of whose polygons are hexagons and each of whose vertices belongs to at most two hexagonal faces.We prove that all CCHC are Kekulean and give formulas for counting the perfect matchings in a series of examples based on expansion of cubic graphs in which the edges are replaced by linear polyacenes of equal length.As a preliminary assessment of the likely stability of molecules with CCHC structure, all-electron quantum chemical calculations are applied to molecular structures based on several CCHC, using either linear or kinked unbranched catafused polyacenes as the expansion motif.The systems examined all have closed shells according to Hückel theory and all correspond to minima on the potential surface, thus passing the most basic test for plausibility as a chemical species.Preliminary indications are that relative energies of isomers are affected by the choice of the catafusene motif, with a preference shown for kinked over linear polyacenes, and for attachment by angular connection at the branching hexagons derived from the vertices of the underlying cubic structure.Avoidance of steric crowding of H atoms appears to be a significant factor in these preferences.

Chat View PDF

On singular signed graphs with nullspace spanned by a full vector: Signed nut graphs

2020-01-01

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

Chat View PDF

Point-ellipse and some other exotic configurations

2019-01-01

Gábor Gévay , Nino Bašić , Jurij Kovič +1 more

In this paper we introduce point-ellipse configurations and point-conic configurations. We study some of their basic properties and describe two interesting families of balanced point-ellipse, respectively point-conic $6$-configurations. The construction … In this paper we introduce point-ellipse configurations and point-conic configurations. We study some of their basic properties and describe two interesting families of balanced point-ellipse, respectively point-conic $6$-configurations. The construction of the first family is based on Carnot's theorem, whilst the construction of the second family is based on the Cartesian product of two regular polygons. Finally, we investigate a point-ellipse configuration based on the regular $24$-cell.

Chat View PDF

Splittable and unsplittable graphs and configurations

2018-08-21

Nino Bašić , Jan Grošelj , Branko Grünbaum +1 more

We prove that there exist infinitely many splittable and also infinitely many unsplittable cyclic $(n_3)$ configurations. We also present a complete study of trivalent cyclic Haar graphs on at most … We prove that there exist infinitely many splittable and also infinitely many unsplittable cyclic $(n_3)$ configurations. We also present a complete study of trivalent cyclic Haar graphs on at most 60 vertices with respect to splittability. Finally, we show that all cyclic flag-transitive configurations with the exception of the Fano plane and the M\"obius-Kantor configuration are splittable.

Chat View PDF

Sizes of pentagonal clusters in fullerenes

2017-05-16

Nino Bašić , Gunnar Brinkmann , Patrick W. Fowler +2 more

Chat View PDF

On the Clar Number of Benzenoid Graphs

2017-01-01

Nino Bašić , István Estélyi , Riste Škrekovski +1 more

A Clar set of a benzenoid graph $B$ is a maximum set of independent alternating hexagons over all perfect matchings of $B$. The Clar number of $B$, denoted by ${\rm … A Clar set of a benzenoid graph $B$ is a maximum set of independent alternating hexagons over all perfect matchings of $B$. The Clar number of $B$, denoted by ${\rm Cl}(B)$, is the number of hexagons in a Clar set for $B$. In this paper, we first prove some results on the independence number of subcubic trees to study the Clar number of catacondensed benzenoid graphs. As the main result of the paper we prove an upper bound for the Clar number of catacondensed benzenoid graphs and characterize the graphs that attain this bound. More precisely, it is shown that for a catacondensed benzenoid graph $B$ with $n$ hexagons ${\rm Cl}(B) \leq [(2n+1)/3]$.

Chat View PDF

Coronoids, patches and generalised altans

2016-01-30

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

Chat View PDF

An algebraic approach to enumerating non-equivalent double traces in graphs

2015-11-30

Nino Bašić , Drago Bokal , Tomas Boothby +1 more

Recently designed biomolecular approaches to build single chain polypeptide polyhedra as molecular origami nanostructures have risen high interest in various double traces of the underlying graphs of these polyhedra. Double … Recently designed biomolecular approaches to build single chain polypeptide polyhedra as molecular origami nanostructures have risen high interest in various double traces of the underlying graphs of these polyhedra. Double traces are walks that traverse every edge of the graph twice, usually with some additional conditions on traversal direction and vertex neighborhood coverage. Given that double trace properties are intimately related to theefficiency of polypeptide polyhedron construction, enumerating all different possible double traces and analyzing their properties is an important step in the construction. In the paper, we study the automorphism group of double traces and present an algebraic approach to this problem, yielding a branch-and-bound algorithm.

Chat View PDF

An algebraic approach to enumerating non-equivalent double traces in graphs

2015-01-01

Nino Bašić , Drago Bokal , Tomas Boothby +1 more

Chat View PDF

Iterated altans and their properties

2015-01-01

Nino Bašić , Tomaž Pisanski

Recently a class of molecular graphs, called altans, became a focus of attention of several theoretical chemists and mathematicians. In this paper we study primary iterated altans and show, among … Recently a class of molecular graphs, called altans, became a focus of attention of several theoretical chemists and mathematicians. In this paper we study primary iterated altans and show, among other things, their connections with nanotubes and nanocaps. The question of classification of bipartite altans is also addressed. Using the results of Gutman we are able to enumerate Kekul\'e structures of several nanocaps of arbitrary length.

Chat View PDF

Common Coauthors

Coauthor	Papers Together
Tomaž Pisanski	21
Patrick W. Fowler	17
Ivan Damnjanović	8
Riste Škrekovski	6
Martin Knor	5
Irene Sciriha	4
Arjana Žitnik	3
Cate S. Anstöter	3
Yaser Alizadeh	2
Jernej Rus	2
Drago Bokal	2
Tomas Boothby	2
Jurij Kovič	2
Kexiang Xu	2
Tomislav Došlić	2
Gábor Gévay	2
Dragan Stevanović	2
Niko Tratnik	1
Gunnar Brinkmann	1
István Estélyi	1
Peter F. Stadler	1
Fowler Patrick W.	1
Pisanski Tomaž	1
Sarah J. Berkemer	1
Nancy Retzlaff	1
Patrick W. Fowler	1
Jörg Fallmann	1
Branko Grünbaum	1
Nico Van Cleemput	1
Sara Sabrina Zemljič	1
Jan Grošelj	1
Thomas Gatter	1

Commonly Cited References

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

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

House of Graphs: A database of interesting graphs

2012-08-16

Gunnar Brinkmann , Kris Coolsaet , Jan Goedgebeur +1 more

Chat View PDF

Charting the space of chemical nut graphs

2020-01-01

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

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

On the construction of graphs of nullity one

1998-02-01

Irene Sciriha

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

On circulant nut graphs

2021-10-18

Ivan Damnjanović , Dragan Stevanović

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

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

On 12-regular nut graphs

2021-07-06

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

Chat View PDF

A constructive enumeration of fusenes and benzenoids

2002-11-01

Gunnar Brinkmann , Gilles Caporossi , Pierre Hansen

Spectra of Graphs

2011-12-15

Andries E. Brouwer , Willem H. Haemers

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

Boundary uniqueness of fusenes

2002-05-01

Xiaofeng Guo , Pierre Hansen , Maolin Zheng

A classification of cubic bicirculants

2006-09-15

Tomaž Pisanski

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

Topological properties of altan-benzenoid hydrocarbons

2014-01-01

Iván Gutman

The main topological characteristics of altan-benzenoids are established. In particular, it is shown that the perimeter of Kekul?an altan-benzenoids is of size 4k , having a destablizing (antiaromatic) energy effect, … The main topological characteristics of altan-benzenoids are established. In particular, it is shown that the perimeter of Kekul?an altan-benzenoids is of size 4k , having a destablizing (antiaromatic) energy effect, similar to (4k)-annulenes.

Chat View PDF

Maximal core size in singular graphs

2009-11-30

Irene Sciriha

A graph G is singular of nullity η if the nullspace of its adjacency matrix G has dimension η . Such a graph contains η cores determined by a basis … A graph G is singular of nullity η if the nullspace of its adjacency matrix G has dimension η . Such a graph contains η cores determined by a basis for the nullspace of G . These are induced subgraphs of singular configurations, the latter occurring as induced subgraphs of G . We show that there exists a set of η distinct vertices representing the singular configurations. We also explore how the nullity controls the size of the singular substructures and characterize those graphs of maximal nullity containing a substructure reaching maximal size.

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

ALTAN DERIVATIVES OF A GRAPH

2014-11-01

Iván Gutman

Altan derivatives of polycyclic conjugated hydrocarbons were recently introduced and studied in theoretical organic chemistry. We now provide a generalization of the altan concept, applicable to any graph. Several earlier … Altan derivatives of polycyclic conjugated hydrocarbons were recently introduced and studied in theoretical organic chemistry. We now provide a generalization of the altan concept, applicable to any graph. Several earlier noticed topological properties of altan derivatives of polycyclic conjugated hydrocarbons are shown to be the properties of all altan derivatives of all graphs. Among these are results pertaining to Kekule structures/perfect matchings, determinant of the adjacency matrix, and graph spectrum.

Fusenes and benzenoids with perfect matchings

2006-09-09

Gunnar Brinkmann , Christian Grothaus , Iván Gutman

A census of small transitive groups and vertex-transitive graphs

2019-06-27

Derek F. Holt , Gordon Royle

Chat View PDF

Kekulé Structures in Benzenoid Hydrocarbons

1988-01-01

S. J. Cyvín , Iván Gutman

Coronoids, patches and generalised altans

2016-01-30

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

Chat View PDF

Practical graph isomorphism, II

2013-09-27

Brendan D. McKay , Adolfo Piperno

Chat View PDF

The boundary-edges code for polyhexes

1996-04-01

Pierre Hansen , Catherine Lebatteux , Maolin Zheng

Iterated altans and their properties

2015-01-01

Nino Bašić , Tomaž Pisanski

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

Partitioning of π-electrons in Rings of Polycyclic Conjugated Hydrocarbons. Part 4. Benzenoids with More Than One Geometric Kekulé Structure Corresponding to the Same Algebraic Kekulé Structure

2004-07-01

Damir Vukičević , Milan Randić , Alexandrù T. Balaban

Allowed Boundary Sequences for Fused Polycyclic Patches and Related Algorithmic Problems

2001-01-12

Michel Deza , Patrick W. Fowler , Viatcheslav Grishukhin

We consider sequences that encode boundary circuits of fused polycycles made up of polygonal faces with p sides, p < or = 6. We give a constructive algorithm for recognizing … We consider sequences that encode boundary circuits of fused polycycles made up of polygonal faces with p sides, p < or = 6. We give a constructive algorithm for recognizing such sequences when p = 5 or 6. A simpler algorithm is given for planar hexagonal sequences. Hexagonal and pentagonal sequences of length at most 8 are tabulated, the former corresponding to planar benzenoid hydrocarbons CxHy with y up to 14.

Regular Skew Polyhedra in Three and Four Dimension, and their Topological Analogues

1938-01-01

H. S. M. Coxeter

Open problems in the spectral theory of signed graphs

2019-08-07

Francesco Belardo , Sebastian M. Cioabă , Jack H. Koolen +1 more

Signed graphs are graphs whose edges get a sign +1 or −1 (the signature). Signed graphs can be studied by means of graph matrices extended to signed graphs in a … Signed graphs are graphs whose edges get a sign +1 or −1 (the signature). Signed graphs can be studied by means of graph matrices extended to signed graphs in a natural way. Recently, the spectra of signed graphs have attracted much attention from graph spectra specialists. One motivation is that the spectral theory of signed graphs elegantly generalizes the spectral theories of unsigned graphs. On the other hand, unsigned graphs do not disappear completely, since their role can be taken by the special case of balanced signed graphs. Therefore, spectral problems defined and studied for unsigned graphs can be considered in terms of signed graphs, and sometimes such generalization shows nice properties which cannot be appreciated in terms of (unsigned) graphs. Here, we survey some general results on the adjacency spectra of signed graphs, and we consider some spectral problems which are inspired from the spectral theory of (unsigned) graphs.

Chat View PDF

Rose window graphs

2008-06-17

Steve Wilson

This paper introduces a family of tetravalent graphs called ";rose window graphs";, denoted R_n(a, r), and investigates their symmetry properties. Four families of these graphs are shown to be edge-transitive … This paper introduces a family of tetravalent graphs called ";rose window graphs";, denoted R_n(a, r), and investigates their symmetry properties. Four families of these graphs are shown to be edge-transitive and it is conjectured that every R_n(a, r) which is edged-transitive belongs to one of these families. Proofs and conjectures about the size of a dart-stabilizer and about regular maps containing these graphs are also offered.

Chat View PDF

Graphical Regular Representations of Non-Abelian Groups, II

1972-12-01

Lewis A. Nowitz , Mark E. Watkins

The present paper is a sequel to the previous paper bearing the same title by the same authors [ 3 ] and which will be hereafter designated by the bold-face … The present paper is a sequel to the previous paper bearing the same title by the same authors [ 3 ] and which will be hereafter designated by the bold-face Roman numeral I . Further results are obtained in determining whether a given finite non-abelian group G has a graphical regular representation. In particular, an affirmative answer will be given if (| G |, 6) = 1. Inasmuch as much of the machinery of I will be required in the proofs to be presented and a perusal of I is strongly recommended to set the stage and provide motivation for this paper, an independent and redundant introduction will be omitted in the interest of economy.

Chat View PDF

Regular polygonal complexes in space, II

2012-10-31

Daniel Pellicer , Egon Schulte

Regular polygonal complexes in euclidean $3$-space $\mathbb {E}^3$ are discrete polyhedra-like structures with finite or infinite polygons as faces and with finite graphs as vertex-figures, such that their symmetry groups … Regular polygonal complexes in euclidean $3$-space $\mathbb {E}^3$ are discrete polyhedra-like structures with finite or infinite polygons as faces and with finite graphs as vertex-figures, such that their symmetry groups are transitive on the flags. The present paper and its predecessor describe a complete classification of regular polygonal complexes in $\mathbb {E}^3$. In Part I we established basic structural results for the symmetry groups, discussed operations on their generators, characterized the complexes with face mirrors as the $2$-skeletons of the regular $4$-apeirotopes in $\mathbb {E}^3$, and fully enumerated the simply flag-transitive complexes with mirror vector $(1,2)$. In this paper, we complete the enumeration of all regular polygonal complexes in $\mathbb {E}^3$ and in particular describe the simply flag-transitive complexes for the remaining mirror vectors. It is found that, up to similarity, there are precisely 25 regular polygonal complexes which are not regular polyhedra, namely 21 simply flag-transitive complexes and $4$ complexes which are $2$-skeletons of regular $4$-apeirotopes in $\mathbb {E}^3$.

Chat View PDF

Polygonal Complexes and Graphs for Crystallographic Groups

2014-01-01

Daniel Pellicer , Egon Schulte

Chat View PDF

Skeletal Geometric Complexes and Their Symmetries

2017-06-29

Egon Schulte , Asia Ivić Weiss

Chat View PDF

π‐Electron currents in larger fully aromatic benzenoids

2011-12-29

Milan Randić , Damir Vukičević , Marjana Novič +1 more

Abstract Recently, we have reported on calculation of π‐electron ring currents in several smaller fully benzenoid hydrocarbons having up to eight fused benzene rings and five Clar π‐aromatic sextets. In … Abstract Recently, we have reported on calculation of π‐electron ring currents in several smaller fully benzenoid hydrocarbons having up to eight fused benzene rings and five Clar π‐aromatic sextets. In contrast to early HMO ring current calculations and more recent ab initio calculations of π‐electron density, our current calculations are based on a graph theoretical model in which contributions to ring currents comes from currents associated with individual conjugated circuits. In this contribution, we consider several larger fully benzenoid hydrocarbons having from 9 to 13 fused rings and from six or seven π‐aromatic sextets. © 2011 Wiley Periodicals, Inc. Int J Quantum Chem, 2011

Flag graphs and their applications in mathematical chemistry for benzenoids

2011-10-20

Tomaž Pisanski , Alexandrù T. Balaban

Infinite series of combinatorially regular polyhedra in three-space

1988-06-01

Peter McMullen , Egon Schulte , J. M. Wills

Handbook of Product Graphs

2011-06-06

Richard H. Hammack , Wilfried Imrich , Sandi Klavžar

Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their … Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures. Results and Algorithms New to the Second Edition: Cancellation results A quadratic recognition algorithm for partial cubes Results on the strong isometric dimension Computing the Wiener index via canonical isometric embedding Connectivity results A fractional version of Hedetniemis conjecture Results on the independence number of Cartesian powers of vertex-transitive graphs Verification of Vizings conjecture for chordal graphs Results on minimum cycle bases Numerous selected recent results, such as complete minors and nowhere-zero flows The second edition of this classic handbook provides a thorough introduction to the subject and an extensive survey of the field. The first three parts of the book cover graph products in detail. The authors discuss algebraic properties, such as factorization and cancellation, and explore interesting and important classes of subgraphs. The fourth part presents algorithms for the recognition of products and related classes of graphs. The final two parts focus on graph invariants and infinite, directed, and product-like graphs. Sample implementations of selected algorithms and other information are available on the books website, which can be reached via the authors home pages.

Cubic vertex-transitive graphs on up to 1280 vertices

2012-09-27

Primož Potočnik , Pablo Spiga , Gabriel Verret

Chat View PDF

Perspectives on Projective Geometry

2011-01-01

Jürgen Richter-Gebert

Kronecker covers, V-construction, unit-distance graphs and isometric point-circle configurations

2013-06-01

Gábor Gévay , Tomaž Pisanski

We call a convex polytope P of dimension 3 admissible if it has the following two properties: (1) for each vertex of P the set of its first-neighbours is coplanar; … We call a convex polytope P of dimension 3 admissible if it has the following two properties: (1) for each vertex of P the set of its first-neighbours is coplanar; (2) all planes determined by the first-neighbours are distinct. It is shown that the Levi graph of a point-plane configuration obtained by V -construction from an admissible polytope P is the Kronecker cover of the 1-skeleton of P . We investigate the combinatorial nature of the V -construction and use it on unit-distance graphs to construct novel isometric point-circle configurations. In particular, we present an infinite series all of whose members are subconfigurations of the renowned

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.

Configurations of Points and Lines

2009-05-15

Branko Grünbaum

This is the only book on the topic of geometric configurations of points and lines. It presents in detail the history of the topic, with its surges and declines since … This is the only book on the topic of geometric configurations of points and lines. It presents in detail the history of the topic, with its surges and declines since its beginning in 1876. It covers all the advances in the field since the revival of interest in geometric configurations some 20 years ago. The author's contributions are central to this revival. In particular, he initiated the study of 4-configurations (that is, those that contain four points on each line, and four lines through each point); the results are fully described in the text. The main novelty in the approach to all geometric configurations is the concentration on their symmetries, which make it possible to deal with configurations of rather large sizes. The book brings the readers to the limits of present knowledge in a leisurely way, enabling them to enjoy the material as well as entice them to try their hand at expanding it.

Graphs with a common eigenvalue deck

2008-08-28

Irene Sciriha

Conjugated circuits and resonance energies of benzenoid hydrocarbons

1976-02-01

Milan Randić

Why Are the Kinked Polyacenes More Stable than the Straight Ones? A Topological Study and Introduction of a New Topological Index of Aromaticity

2008-06-12

Arkadiusz Ciesielski , Tadeusz M. Krygowski , Michał K. Cyrański

A topological model for estimating the stability of benzenoid hydrocarbons (BHs) is presented showing an acceptable linear dependence on Hess−Schaad resonance energy per π-electron values. The topological measure of stability … A topological model for estimating the stability of benzenoid hydrocarbons (BHs) is presented showing an acceptable linear dependence on Hess−Schaad resonance energy per π-electron values. The topological measure of stability is accessible by use of pencil calculation and is based on counting cis-type fragments of double bonds in all canonical structures of a given BH. Evidence is given that infinite chains of straight linear polyacenes are always less stable than the kinked ones.