On the role of hypercubes in the resonance graphs of benzenoid graphs

The resonance graph R(B) of a benzenoid graph B has the perfect matchings of B as vertices, two perfect matchings being adjacent if their symmetric difference forms the edge set of a hexagon of B. A family P of pair-wise disjoint hexagons of a benzenoid graph B is resonant in B if B-P contains at least one perfect matching, or if B-P is empty. It is proven that there exists a surjective map f from the set of hypercubes of R(B) onto the resonant sets of B such that a k-dimensional hypercube is mapped into a resonant set of cardinality k.     

Relations between Clar structures, Clar covers, and the sextet-rotation tree of a hexagonal system

Sextet rotations of the perfect matchings of a hexagonal system H are represented by the sextet-rotation-tree R(H), a directed tree with one root. In this article we find a one-to-one correspondence between the non-leaves of R(H) and the Clar covers of H, without alternating hexagons. Accordingly, the number (nl) of non-leaves of R(H) is not less than the number (cs) of Clar structures of H. We obtain some simple necessary and sufficient conditions, and a criterion for cs=nl, that are useful for the calculation of Clar polynomials. A procedure for constructing hexagonal systems with cs<nl is provided in terms of normal additions of hexagons.     

FORCING BONDS OF A BENZENOID SYSTEM

ＦＯＲＣＩＮＧＢＯＮＤＳＯＦＡＢＥＮＺＥＮＯＩＤＳＹＳＴＥＭＺＨＡＮＧＦＵＪＩ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＸｉａｍｅｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉａｍｅｎ８５００４６，Ｃｈｉｎａ）ＬＩＸＵＥＬＩＡＮＧ（ＤｅｐａｒｔｍｅｎｔｏｆＡｐ...     

Hypergraphs and the Clar problem in hexagonal systems

We show that for a hypergraph H that is separable and has the Helly property, the perfect matchings of H are the strongly stable sets of the line graph of H. Also, we show that the hypergraph generated by a hexagonal system is separable and has the Helly property. Finally, we note that the Clar problem of a hexagonal system is a minimum cardinality perfect matching problem of the hypergraph generated by the hexagonal system. Hence, the Clar problem of a hexagonal system is a minimum cardinality strongly stable set problem in the line graph of the hypergraph generated by the hexagonal system.     

Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs

A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in O(n²) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.     

Non-zero component union graph of a finite-dimensional vector space

In this paper, we introduce a graph structure, called non-zero component union graph on finite-dimensional vector spaces. We show that the graph is connected and find its domination number, clique number and chromatic number. It is shown that two non-zero component union graphs are isomorphic if and only if the base vector spaces are isomorphic. In case of finite fields, we study the edge-connectivity and condition under which the graph is Eulerian. Moreover, we provide a lower bound for the independence number of the graph. Finally, we come up with a structural characterization of non-zero component union graph.     

The reduced expressions in a Coxeter system with a strictly complete Coxeter graph

Let (W,S)$(W,S)$ be a Coxeter system with a strictly complete Coxeter graph. The present paper concerns the set Red(z)$\mathrm{Red}(z)$ of all reduced expressions for any z∈W$z\in W$. By associating each bc-expression to a certain symbol, we describe the set Red(z)$\mathrm{Red}(z)$ and compute its cardinal |Red(z)|$|\mathrm{Red}(z)|$ in terms of symbols. An explicit formula for |Red(z)|$|\mathrm{Red}(z)|$ is deduced, where the Fibonacci numbers play a crucial role.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

Problems on matchings and independent sets of a graph

Let $G$ be a finite simple graph. For $X?V\left(G\right)$, the difference of $X$, $d\left(X\right)?\left|X\right|?\left|N\left(X\right)\right|$ where $N\left(X\right)$ is the neighborhood of $X$ and $max\{d\left(X\right):X?V\left(G\right)\}$ is called the critical difference of $G$. $X$ is called a critical set if $d\left(X\right)$ equals the critical difference and $\ker \left(G\right)$ is the intersection of all critical sets. $\mathrm{diadem}\left(G\right)$ is the union of all critical independent sets. An independent set $S$ is an inclusion minimal set with$d\left(S\right)>0$ if no proper subset of $S$ has positive difference.A graph $G$ is called a König–Egerváry graph if the sum of its independence number $\alpha \left(G\right)$ and matching number $\mu \left(G\right)$ equals $\left|V\left(G\right)\right|$.In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set $S$ with $d\left(S\right)>0$ is at least the critical difference of the graph.We also give a new short proof of the inequality $\left|\ker \left(G\right)\right|+\left|\mathrm{diadem}\left(G\right)\right|\le 2\alpha \left(G\right)$.A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph $G$, the critical difference equals $\alpha \left(G\right)?\mu \left(G\right)$, is proved.We also make an observation about $\ker \left(G\right)$ using Edmonds–Gallai Structure Theorem as a concluding remark.     

First eigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph

Let G be a mixed graph and let L(G) be the Laplacian matrix of the graph G. The first eigenvalue and the first eigenvectors of G are respectively referred to the least nonzero eigenvalue and the corresponding eigenvectors of L(G). In this paper we focus on the properties of the first eigenvalue and the first eigenvectors of a nonsingular unicyclic mixed graph (abbreviated to a NUM graph). We introduce the notion of characteristic set associated with the first eigenvectors, and then obtain some results on the sign structure of the first eigenvectors. By these results we determine the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order and fixed girth, and the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order.     

Spectral asymptotics and regularized traces for Dirac operators on a star-shaped graph

In this article, we consider the spectral problems for Dirac operators on a star-shaped graph. First, we derive the asymptotic expressions of the eigenvalues and then explicitly establish the regularized trace formulae for the operators in terms of the coefficients of the operators.     

The color space of a graph

If k is a prime power, and G is a graph with n vertices, then a k‐coloring of G may be considered as a vector in $\mathbb{GF}$(k)ⁿ. We prove that the subspace of $\mathbb{GF}$(3)ⁿ spanned by all 3‐colorings of a planar triangle‐free graph with n vertices has dimension n. In particular, any such graph has at least n − 1 nonequivalent 3‐colorings, and the addition of any edge or any vertex of degree 3 results in a 3‐colorable graph. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 234–245, 2000     

On minimum rank and zero forcing sets of a graph

For a graph G on n vertices and a field F, the minimum rank of G over F, written as mr^F(G), is the smallest possible rank over all n×n symmetric matrices over F whose (i,j)th entry (for ) is nonzero whenever ij is an edge in G and is zero otherwise. The maximum nullity of G over F is M^F(G)=n-mr^F(G). The minimum rank problem of a graph G is to determine mr^F(G) (or equivalently, M^F(G)). This problem has received considerable attention over the years. In [F. Barioli, W. Barrett, S. Butler, S.M. Cioab?, D. Cvetkovi?, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovi?, H. van der Holst, K.V. Meulen, A.W. Wehe, AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628-1648], a new graph parameter Z(G), the zero forcing number, was introduced to bound M^F(G) from above. The authors posted an attractive question: What is the class of graphs G for which Z(G)=M^F(G) for some field F? This paper focuses on exploring the above question.     

The interval function of a connected graph and road systems

Let V be a finite nonempty set. In this paper, a road system on V (as a generalization of the set of all geodesics in a connected graph G with V(G)=V) and an intervaloid function on V (as a generalization of the interval function (in the sense of Mulder) of a connected graph G with V(G)=V) are introduced. A natural bijection of the set of all intervaloid functions on V onto the set of all road systems on V is constructed. This bijection enables to deduce an axiomatic characterization of the interval function of a connected graph G from a characterization of the set of all geodesics in G.     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On the power graph and the reduced power graph of a finite group

In this paper, for a finite group, we investigate to what extent its directed (resp. undirected) reduced power graph determines its directed power graph (resp. reduced power graph). Moreover, we investigate the determination of the orders of the elements of a finite group from its directed (resp. undirected) reduced power graph. Consequently, we show that some classes of finite groups are recognizable from their undirected reduced power graphs. Also, we study the relationship between the isomorphism classes of groups corresponding to the equivalence relations induced by the isomorphism of each of these graphs on the set of all finite groups.     

The girth of a 4-homogeneous bipartite graph

In this paper, it is proved that the girth of a 4-homogeneous bipartite graph with valency greater than 2 is at most 12.