The Hosoya polynomial decomposition for catacondensed benzenoid graphs

For a graph G with the vertex set V(G), we denote by d(u,v) the distance between vertices u and v in G, by d(u) the degree of vertex u. The Hosoya polynomial of G is H(G)=∑_{u,v}⊆V(G)x^d(u,v). The partial Hosoya polynomials of G are for positive integer numbers m and n. It is shown that H(G₁)−H(G₂)=x²(x+1)²(H₃₃(G₁)−H₃₃(G₂)),H₂₂(G₁)−H₂₂(G₂)=(x²+x−1)²(H₃₃(G₁)−H₃₃(G₂)) and H₂₃(G₁)−H₂₃(G₂)=2(x²+x−1)(H₃₃(G₁)−H₃₃(G₂)) for arbitrary catacondensed benzenoid graphs G₁ and G₂ with equal number of hexagons. As an application, we give an affine relationship between H(G) with two other distance-based polynomials constructed by Gutman [I. Gutman, Some relations between distance-based polynomials of trees, Bulletin de l’Académie Serbe des Sciences et des Arts (Cl. Math. Natur.) 131 (2005) 1-7].     

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.     

The Clar formulas of a benzenoid system and the resonance graph

It is shown that the number of Clar formulas of a Kekuléan benzenoid system B is equal to the number of subgraphs of the resonance graph of B isomorphic to the Cl(B)-dimensional hypercube, where Cl(B) is the Clar number of B.     

The fractional metric dimension of permutation graphs

Let G =(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V(G) and for U■V(G), let g(U) =∑s∈Ug(s). A real-valued function g : V(G) → [0, 1] is a resolving function of G if g(RG{x, y}) ≥ 1 for any two distinct vertices x, y ∈ V(G). The fractional metric dimension dimf(G)of a graph G is min{g(V(G)) : g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ : V(G1) → V(G2) be a bijection. Then, a permutation graph Gσ =(V, E) has the vertex set V = V(G1) ∪ V(G2) and the edge set E = E(G1) ∪ E(G2) ∪ {uv | v = σ(u)}. First,we determine dimf(T) for any tree T. We show that 1 dimf(Gσ) ≤1/2(|V(G)| + |S(G)|) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any ε 0, there exists a permutation graph Gσ such that dimf(Gσ)- 1 ε. We give examples showing that neither is there a function h1 such that dimf(G) h1(dimf(Gσ)) for all pairs(G, σ), nor is there a function h2 such that h2(dimf(G)) dimf(Gσ) for all pairs(G, σ). Furthermore,we investigate dimf(Gσ) when G is a complete k-partite graph or a cycle.     

On the metric dimension of incidence graphs

A resolving set for a graph $\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The metric dimension$\mu \left(\Gamma \right)$ is the smallest size of a resolving set for $\Gamma$. We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that $\mu \left(\Gamma \right)=O(\sqrt{n}logn)$ (where $n$ is the number of vertices).     

The relationship between the threshold dimension of split graphs and various dimensional parameters

Let the coboxicity of a graph G be denoted by cob(G), and the threshold dimension by t(G). For fixed k≥3, determining if cob(G)≥k and t(G)≤k are both NP-complete problems. We show that if G is a comparability graph, then we can determine if cob(G)≤2 in polynomial time. This result shows that it is possible to determine if the interval dimension of a poset equals 2 in polynomial time. If the clique covering number of G is 2, we show that one can determine if t(G)≤2 in polynomial time. Sufficient conditions on G are given for cob(G)≤2 and for t(G)≤2.     

On strong metric dimension of graphs and their complements

A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices S■V(G) is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim(G), is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim(G) equals 1, n-1, or n-2, respectively. We give a Nordhaus-Gaddum-type result for the strong metric dimension of a graph and its complement: for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim(G)+sdim(G)≤2( n-2). It is readily seen that sdim(G)+sdim(G)=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim(G)+sdim(G)=2(n 2) if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim(G)+sdim(G)≤2(n-3) if G is a tree; we also show that 4≤sdim(G)+sdim(G)≤2(n-3) if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim(G)+sdim(G)=2(n-3) when G is a tree or a unicyclic graph.     

Cube-complements of generalized Fibonacci cubes

The generalized Fibonacci cube $Q_h\left(f\right)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. If $G$ is an induced subgraph of $Q_h$, then the cube-complement of $G$ is the graph induced by the vertices of $Q_h$ which are not in $G$. In particular, the cube-complement of a generalized Fibonacci cube $Q_h\left(f\right)$ is the subgraph of $Q_h$ induced by the set of all vertices that contain $f$ as a substring. The questions whether a cube-complement of a generalized Fibonacci cube is (i) connected, (ii) an isometric subgraph of a hypercube or (iii) a median graph are studied. Questions (ii) and (iii) are completely solved, i.e. the sets of binary strings that allow a graph of this class to be an isometric subgraph of a hypercube or a median graph are given. The cube-complement of a daisy cube is also studied.     

Fibonacci identities via the determinant of tridiagonal matrix

In this paper, using the method of Laplace expansion to evaluate the determinant tridiagonal matrices, we construct a kind of determinants to give new proof of the Fibonacci identities.     

Products of unit distance graphs

Some graphs admit drawings in the Euclidean plane (k-space) in such a (natural) way, that edges are represented as line segments of unit length. We say that they have the unit distance property.The influence of graph operations on the unit distance property is discussed. It is proved that the Cartesian product preserves the unit distance property in the Euclidean plane, while graph union, join, tensor product, strong product, lexicographic product and corona do not. It is proved that the Cartesian product preserves the unit distance property also in higher dimensions.     

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.     

A polynomial-time algorithm for the paired-domination problem on permutation graphs

A set S of vertices in a graph H=(V,E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and π be its corresponding permutation. In this paper we present an O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges.     

关于一类Fibonacci行列式的计算

研究了一类由Fibonacci数组成的特殊行列式Dn(m,k)的计算问题,并给出了一个有趣的恒等式     

以Fibonacci数为模的广义Fibonacci等距子列的周期

给出广义Fibonacci等距子列的定义,求出以Fibonacci数fm为模的模数列的周期,由此得到求广义Fibonacci数列模fm的周期的算法.