Search

Abstract A (4, 6)-fullerene graph G is a plane cubic graph whose faces are squares and hexagons. A resonant set of G is a set of pairwise disjoint faces of G such that the boundaries of such faces are M -alternating cycles for a perfect matching M of G. A resonant set of G is referred to as sextet pattern whenever it only includes hexagonal faces. It was shown that the cardinality of a maximum resonant set of G is equal to the maximum forcing number. In this article, we obtain an expression for the cardinality of a maximum sextet pattern (or Clar formula) of G , which is less than the cardinality of a maximum resonant set of G by one or two. Moreover we mainly characterize all the maximum sextet patterns of G. Via such characterizations we get a formula to count maximum sextet patterns of G only depending on the order of G and the number of fixed subgraphs J 1 of G , where the count equals the coefficient of the term with largest degree in its sextet polynomial. Also the number of Clar structures of G is obtained. [ABSTRACT FROM AUTHOR]

A matching preclusion set of a graph is an edge set whose deletion results in a graph without perfect matchings or almost perfect matchings. The Cartesian product of n paths is called an n -grid graph. In this paper, we study the matching preclusion problems for n -grid graphs and obtain the following results. If an n -grid graph has an even order, then it has the matching preclusion number n , and every optimal matching preclusion set is trivial except for the case of P 2 m □ P 3 , the Cartesian product of a path on 2 m vertices and a path on 3 vertices, when the nontrivial optimal matching preclusion sets are completely characterized. If the n -grid graph has an odd order, then it has the matching preclusion number n + 1 , and all the optimal matching preclusion sets are characterized. [ABSTRACT FROM AUTHOR]

It is useful to consider faulty networks because node faults or link faults may occur in networks. In this paper, we investigate hamiltonian properties of conditional faulty hypercubes. Let F be a set of faulty edges in hypercube Q n with n ≥ 4 and | F | ≤ 3 n − 11 . We prove that there still exists a hamiltonian path in Q n − F joining any two vertices of different partite sets if the following two constraints are satisfied: ( 1 ) the degree of every vertex in Q n − F is at least 2, and ( 2 ) there is at most one vertex with degree 2 in Q n − F . [ABSTRACT FROM AUTHOR]

In interconnection networks, matching preclusion is a measure of robustness when there is a link failure. Let G be a graph with an even number of vertices. The matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching, and the conditional matching preclusion number of G is the minimum number of edges whose deletion results in a graph with no isolated vertices and without a perfect matching. In this paper, we study these problems for undirected binary de Bruijn graph U B ( n ) . As an essential preparation, we obtain conditional edge-fault Hamiltonicity of binary de Bruijn graph B ( n ) . Then we obtain matching preclusion number and conditional matching preclusion number of U B ( n ) for n ⩾ 4 and classify all optimal matching preclusion sets and optimal conditional matching preclusion sets. [ABSTRACT FROM AUTHOR]

An edge of a graph G is called an anti-forcing edge (or forcing single edge) if G has a unique perfect matching not containing this edge. It has been known for two decades that a hexagonal system has an anti-forcing edge if and only if it is a truncated parallelogram. A connected subgraph G of a hexagonal system is called a single coronoid system if G has exactly one non-hexagonal interior face and each edge belongs to a hexagon of G . In this paper, we show that a single coronoid system with an anti-forcing edge can be obtained by gluing a truncated parallelogram with a generalized hexagonal system which has a unique perfect matching and can be obtained by attaching two additional pendant edges to a hexagonal system, and the latter can be constructed from one hexagon case by applying five modes of hexagon addition. Such graphs are half essentially disconnected coronoid systems in the rheo classification. So computing the number of perfect matchings of such graphs is reduced to that of two hexagonal systems. [ABSTRACT FROM AUTHOR]

The anti-forcing number of a perfect matching M of a graph G is the minimal number of edges not in M whose removal to make M as a unique perfect matching of the resulting graph. The set of anti-forcing numbers of all perfect matchings of G is the anti-forcing spectrum of G . In this paper, we characterize the plane elementary bipartite graph whose minimum anti-forcing number is one. We show that the maximum anti-forcing number of a graph is at most its cyclomatic number. In particular, we characterize the graphs with the maximum anti-forcing number achieving the upper bound, such extremal graphs are a class of plane bipartite graphs. Finally, we determine the anti-forcing spectrum of an even polygonal chain in linear time. [ABSTRACT FROM AUTHOR]

The anti-forcing number of a perfect matching M of a graph G is the minimal number of edges not in M whose removal makes M a unique perfect matching of the resulting graph. The anti-forcing spectrum of G is the set of anti-forcing numbers over all perfect matchings of G: In this paper, we prove that the anti-forcing spectrum of any cata-condensed hexagonal system is continuous, that is, it is a finite set of consecutive integers. [ABSTRACT FROM AUTHOR]

Let G be a plane bipartite graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M such that S is not contained by other perfect matchings of G . The minimum cardinality of forcing sets of M is called the forcing number of M , denoted by f ( G , M ) . Pachter and Kim established a minimax result: for any perfect matching M of G , f ( G , M ) is equal to the maximum number of disjoint M -alternating cycles in G . For a polyomino graph H , we show that for every perfect matching M of H with the maximum or second maximum forcing number, f ( H , M ) is equal to the maximum number of disjoint M -alternating squares in H . This minimax result does not hold in general for other perfect matchings of H with smaller forcing number. [ABSTRACT FROM AUTHOR]

A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper, we show that if K is a maximum resonant set of P, then P − K has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to the cardinality of a maximum resonant set. This confirms a conjecture of Xu et al. [26]. We also show that if K is a maximal alternating set of P, then P − K has a unique perfect matching. [ABSTRACT FROM AUTHOR]

A graph of order n is p -factor-critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1-factor-critical graphs and 2-factor-critical graphs are factor-critical graphs and bicritical graphs, respectively. It is well known that every connected vertex-transitive graph of odd order is factor-critical and every connected nonbipartite vertex-transitive graph of even order is bicritical. In this article, we show that a simple connected vertex-transitive graph of odd order at least five is 3-factor-critical if and only if it is not a cycle. [ABSTRACT FROM AUTHOR]

The bondage number of a graph is the cardinality of a minimum edge set whose removal from results in a graph with the domination number greater than that of . It is a parameter to measure the vulnerability of a communication network under link failure. In this paper, we obtain the exact value of the bondage number of the strong product of a complete graph and a path. That is, for any two integers and , if ; if (mod 3); if (mod 3). Furthermore, we determine the exact value of the bondage number of the strong product of a complete graph and a special starlike tree. [ABSTRACT FROM AUTHOR]

A binary string f is a factor of string u if f appears as a sequence of | f | consecutive bits of u , where | f | denotes the length of f . Generalized Fibonacci cube Q d ( f ) is the graph obtained from the d -cube Q d by removing all vertices that contain a given binary string f as a factor. A binary string f is called good if Q d ( f ) is an isometric subgraph of Q d for all d ≥ 1 , it is called bad otherwise. The index of a binary string f , denoted by B ( f ) , is the smallest integer d such that Q d ( f ) is not an isometric subgraph of Q d . Ilić, Klavžar and Rho conjectured that B ( f ) < 2 | f | for any bad string f . They also conjectured that if Q d ( f ) is an isometric subgraph of Q d , then Q d ( f f ) is an isometric subgraph of Q d . We confirm these two conjectures by obtaining a basic result: if there exist p -critical words for Q B ( f ) ( f ) , then p = 2 or p = 3 . [ABSTRACT FROM AUTHOR]

Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matchings of G. The smallest cardinality of a forcing set of M is called forced matching number, denoted by f( G, M). Among all perfect matchings of G, the maximum forcing matching number is called the maximum forcing number of G, denoted by F( G). In this paper, we show that the maximum forcing numbers of cylindrical grid $$P_{2m}\times C_{2n+1}$$ is $$m(n+1)$$ by choosing a suitable independent set of this graph. This solves an open problem proposed by Afshani et al. (Australas J Combin 30:147-160, ). Moreover, we obtain that the maximum forcing numbers of two classes of toroidal 4-8 lattice and two classes of Klein bottle 4-8 lattice are all equal to the number of squares pq. [ABSTRACT FROM AUTHOR]

Ruskey and Savage asked the following question: does every matching of a hypercube $$Q_{n}$$ for $$n\ge 2$$ extend to a Hamiltonian cycle of $$Q_{n}$$ ? Fink confirmed that the question is true for every perfect matching, thus solved Kreweras' conjecture. In this paper we prove that every matching of at most $$3n-10$$ edges can be extended to a Hamiltonian cycle of $$Q_{n}$$ for $$n\ge 4$$ . [ABSTRACT FROM AUTHOR]

A graph G is said to be determined by its permanental spectrum if any graph having the same permanental spectrum as G is isomorphic to G . In this paper, we introduce the permanental nullity of a graph, the multiplicity of the number zero in the permanental spectrum of a graph, to study graphs determined by their permanental spectra. First, we determine all graphs of order n whose permanental nullities are n − 2 , n − 3 , n − 4 and n − 5 , respectively. Then, we show that all graphs with the permanental nullity n − 2 , n − 3 , or n − 5 , and all non-bipartite graphs with the permanental nullity n − 4 are determined by their permanental spectra. In particular, we prove that the complete bipartite graphs are determined by their permanental spectra. [ABSTRACT FROM AUTHOR]

A fullerene graph F is a planar cubic graph with exactly 12 pentagonal faces and other hexagonal faces. A set H of disjoint hexagons of F is called a resonant pattern (or sextet pattern ) if F has a perfect matching M such that every hexagon in H is M -alternating. F is said to be k - resonant if any i ( 0 ≤ i ≤ k ) disjoint hexagons of F form a resonant pattern. It was known that each fullerene graph is 1-resonant and there are only nine fullerene graphs that are 3-resonant. In this paper, we show that the fullerene graphs which do not contain the subgraph L or R as illustrated in Fig. 1 are 2-resonant except for the specific eleven graphs. This result implies that each IPR fullerene is 2-resonant. [ABSTRACT FROM AUTHOR]

A lollipop graph, denoted by, is a graph obtained by appending a cycleto a pendant vertex of a path. It is known that the lollipop graphs are determined by their spectra [Haemers WH, Liu X, Zhang Y. Spectral characterizations of lollipop graphs. Linear Algebra Appl. 2008;428:2415–2423; Boulet R, Jouve B. The lollipop graph is determined by its spectrum. Electron. J. Combin. 2008;15:#R74]. In this paper, we consider whether the lollipop graphs can be determined by the permanental polynomial. We show that() andare determined by their permanental polynomials when restricted to connected graphs, and in general() cannot be determined by their permanental polynomials even when restricted to connected graphs. In particular, we find disconnected copermanental mates offorand connected copermanental mates of,,, andfor, respectively. [ABSTRACT FROM PUBLISHER]

Abstract: A global forcing set of a simple connected graph with a perfect matching is a set of edges such that no two different perfect matchings of coincide on it. The minimum size of global forcing sets of is called the global forcing number of . Došlić proved that the global forcing number of a cata-condensed hexagonal system is equal to the number of its hexagons. In this paper, we consider normal hexagonal systems. By giving a criterion to determine if two adjacent hexagons of normal hexagonal systems form a nice subgraph, we establish a sharp lower bound on the global forcing number of normal hexagonal systems. For a kind of normal hexagonal systems called “divisible hexagonal systems”, we get a formula for the global forcing number and obtain a linear algorithm for finding a minimum global forcing set. [Copyright &y& Elsevier]

Abstract: A graph is an -graph if its vertices can be labeled by binary vectors in such a way that the Hamming distance between the binary addresses is, up to scale, the distance in the graph between the corresponding vertices. In this note, we study when the result of gluing two -graphs along an edge is an -graph. If at least one of the constituent graphs is bipartite, then the resulting graph is also an -graph. For two nonbipartite -graphs, this is not always the case. [Copyright &y& Elsevier]

This paper extends the methodology for the construction of odd polyhedral links. Building blocks are odd chain tangles, each of which consists of finitely many $$2n+1$$-twist tangles for any nonnegative integer $$n$$. For any polyhedral graph $$G$$, replacing each edge with an odd chain tangle results in an infinite collection of odd polyhedral links. The relationship between the HOMFLY polynomials of these odd links and the $$Q^{d}$$-polynomial of $$G$$ is established. It leads to the determination of the span of the HOMFLY polynomial, the bound on the braid index and the genus of each odd link. Our results show that these indices depend not only on the building blocks but also on the graph $$G.$$ [ABSTRACT FROM AUTHOR]

Abstract: For a connected graph , an edge-cut is called a restricted edge-cut if contains no isolated vertices. And is said to be super restricted edge-connected, for short super-, if each minimum restricted edge-cut of isolates an edge. Let denote the set of the minimum degree vertices of . In this paper, for a super- graph with diameter and minimum degree , we show that the induced subgraph contains no complete graph . Applying this property we characterize the super restricted edge connected graphs with diameter which satisfy a type of neighborhood condition. This result improves the previous related one which was given by Wang et al. [S. Wang, J. Li, L. Wu, S. Lin, Neighborhood conditions for graphs to be super restricted edge connected, Networks 56 (2010) 11–19]. [Copyright &y& Elsevier]

Abstract: The Fibonacci (, )-cube is an interconnection topology, which unifies a wide range of connection topologies, such as hypercube, Fibonacci cube, postal network, etc. It is known that the Fibonacci cubes are median graphs [S. Klavžar, On median nature and enumerative properties of Fibonacci-like cubes, Discrete Math. 299 (2005) 145–153]. The question for determining which Fibonacci (, )-cubes are median graphs is solved completely in this paper. We show that Fibonacci (, )-cubes are median graphs if and only if either and , or and . [Copyright &y& Elsevier]

Abstract: Let G be a graph and the adjacency matrix of G. The permanental polynomial of G is defined as . If two graphs G and H have the same permanental polynomial, then G is called a per-cospectral mate of H. A graph G is said to be characterized by its permanental polynomial if all the per-cospectral mates of G are isomorphic to G. It is shown that complete graphs, stars, regular complete bipartite graphs, and odd cycles are characterized by their permanental polynomials. We prove that in general the permanental polynomial cannot characterize the paths and even cycles. In particular, for each and , we can find non-isomorphic per-cospectral mates of and , respectively. When we restrict our consideration to connected graphs, both the paths and even cycles are characterized by their permanental polynomials. [Copyright &y& Elsevier]

Abstract: A connected graph with at least vertices is said to have property if for any two disjoint matchings and of sizes and respectively, has a perfect matching such that and . Let be the smallest integer such that no graphs embedded in the surface are -extendable. It has been shown that no graphs embedded in some scattered surfaces as the sphere, projective plane, torus and Klein bottle are . In this paper, we show that this result holds for all surfaces. Furthermore, we obtain that for each integer , if a graph embedded in a surface has too many vertices, then does not have property . [Copyright &y& Elsevier]

Abstract: The permanental polynomial of a graph is . From the result that a bipartite graph admits an orientation such that every cycle is oddly oriented if and only if it contains no even subdivision of , Yan and Zhang showed that the permanental polynomial of such a bipartite graph can be expressed as the characteristic polynomial of the skew adjacency matrix . In this note we first prove that this equality holds only if the bipartite graph contains no even subdivision of . Then we prove that such bipartite graphs are planar. Unexpectedly, we mainly show that a 2-connected bipartite graph contains no even subdivision of if and only if it is planar 1-cycle resonant. This implies that each cycle is oddly oriented in any Pfaffian orientation of a 2-connected bipartite graph containing no even subdivision of . Accordingly, we give a way to compute the permanental polynomials of such graphs by Pfaffian orientation. [Copyright &y& Elsevier]

Abstract: Aldred and Plummer proved that every 6-connected even graph minimally embedded on the torus or the Klein bottle is and [R.E.L. Aldred, M.D. Plummer, Restricted matching in graphs of small genus, Discrete Math. 308 (2008) 5907–5921]. In this paper, we can remove the upper bounds on by showing that every even 6-regular graph embedded on the torus or the Klein bottle has property and for arbitrary . [Copyright &y& Elsevier]

Abstract: Dimer statistics is a central problem in statistical physics. In this paper the enumerations of close-packed dimers of honeycomb lattices on Klein bottle, Möbius strip and cylinder are considered. By establishing a Pfaffian orientation or a crossing orientation, and then computing the determinants of the skew-symmetric matrices of the resulting orientation graphs, we obtain explicit expressions of the number of close-packed dimers of the Klein-bottle polyhex, the Möbius polyhex and the cylindrical polyhex. [Copyright &y& Elsevier]

Abstract: Let be a graph that admits a perfect matching . A forcing set for a perfect matching is a subset of such that it is contained in no other perfect matchings of . The smallest cardinality of forcing sets of is called the forcing number of . Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron–nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two. [Copyright &y& Elsevier]

Let G be a connected graph. The resistance distance between any two vertices of G is defined as the net effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index is the sum of resistance distances between all pairs of vertices in G. Zhou and Trinajstić (Chem Phys Lett 455(1-3):120-123, ) obtained a Nordhaus-Gaddum-type result for the Kirchhoff index by obtaining lower and upper bounds for the sum of the Kirchhoff index of a graph and its complement. In this paper, by making use of the Cauchy-Schwarz inequality, spectral graph theory and Foster's formula, we give better lower and upper bounds. In particular, the lower bound turns out to be tight. Furthermore, we establish lower and upper bounds on the product of the Kirchhoff index of a graph and its complement. [ABSTRACT FROM AUTHOR]

Abstract: The Fibonacci (, )-cube is an interconnection topology, which includes a wide range of connection topologies as its special cases, such as the Fibonacci cube, the postal network, etc. Klavžar and Žigert [S. Klavžar, P. Žigert, Fibonacci cubes are the resonance graphs of fibonaccenes, Fibonacci Quart. 43 (2005) 269–276] proved that Fibonacci cubes are just the -transformation graphs (also called resonance graphs) of fibonaccenes, i.e. zigzag hexagonal chains. In this paper, we determine all Fibonacci (, )-cubes which can be the -transformation graphs of perfect matchings of plane (bipartite) graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we give some results on Laplacian spectral radius of graphs with cut vertices, and as their applications, we also determine the unique graph with the largest Laplacian spectral radius among all unicyclic graphs with vertices and diameter , . [ABSTRACT FROM AUTHOR]

Abstract: A benzenoid system is -resonant if any set of no more than disjoint hexagons is a resonant pattern, i.e, has a perfect matching. In 1990’s M. Zheng constructed the 3-resonant benzenoid systems and showed that they are maximally resonant, that is, they are -resonant for all . Recently, the equivalence of 3-resonance and maximal resonance has been shown to be valid also for coronoid systems, carbon nanotubes, polyhexes in tori and Klein bottles, and fullerene graphs. So our main problem is to investigate the extent of graphs possessing this interesting property. In this paper, by replacing the above hexagons with even faces, we define -resonance of graphs in surfaces, possibly with boundary, in a unified way. Some exceptions exist. For plane polygonal systems tessellated with polygons of even size at least six such that all inner vertices have the same degree three and the others have degree two or three, we show that such 3-resonant polygonal systems are indeed maximally resonant. They can be constructed by gluing and lapping operations on three types of basic graphs. [ABSTRACT FROM AUTHOR]

Abstract: A set of disjoint faces of a plane bipartite graph is a resonant pattern if has a perfect matching such that the boundary of each face in is an -alternating cycle. An elementary result was obtained [Discrete Appl. Math. 105 (2000) 291–311]: a plane bipartite graph is 1-extendable if and only if every face forms a resonant pattern. In this paper we show that for a 2-extendable plane bipartite graph, any pair of disjoint faces form a resonant pattern, and the converse does not necessarily hold. As an application, we show that all boron–nitrogen (B–N) fullerene graphs are 2-resonant, and construct all the 3-resonant B–N fullerene graphs, which are all -resonant for any positive integer . Here a B–N fullerene graph is a plane cubic graph with only square and hexagonal faces, and a B–N fullerene graph is -resonant if any disjoint faces form a resonant pattern. Finally, the cell polynomials of 3-resonant B–N fullerene graphs are computed. [Copyright &y& Elsevier]

Abstract: Let denote the graph obtained by attaching pendent edges to a vertex of complete graph , and the graph obtained by attaching pendent edges to a vertex of . In this paper, we first prove that the graph and its complement are determined by their adjacency spectra, and by their Laplacian spectra. Then we prove that is determined by its Laplacian spectrum, as well as its adjacency spectrum if is odd, and find all its cospectral graphs for . [Copyright &y& Elsevier]

Abstract: A fullerene graph is a cubic 3-connected plane graph with (exactly 12) pentagonal faces and hexagonal faces. Let be a fullerene graph with vertices. A set of mutually disjoint hexagons of is a sextet pattern if has a perfect matching which alternates on and off every hexagon in . The maximum cardinality of sextet patterns of is the Clar number of . It was shown that the Clar number is no more than . Many fullerenes with experimental evidence attain the upper bound, for instance, and . In this paper, we characterize extremal fullerene graphs whose Clar numbers equal . By the characterization, we show that there are precisely 18 fullerene graphs with 60 vertices, including , achieving the maximum Clar number 8 and we construct all these extremal fullerene graphs. [Copyright &y& Elsevier]

Abstract: A perfect 2-matching of a graph is a spanning subgraph of such that each component of is either an edge or a cycle. A graph is said to be 2-matching-covered if every edge of lies in some perfect 2-matching of . A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if is not 2-matching-covered for all edges of . We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than and is 2 and to prove that a minimal 2-matching-covered graph other than cannot contain a complete subgraph with at least 4 vertices. [Copyright &y& Elsevier]

Abstract: Let , and be the join, corona and cluster of graphs and , respectively. In this paper, Kirchhoff index formulae of these composite graphs are given. [Copyright &y& Elsevier]

Abstract: For a positive integer , an edge-cut of a connected graph is an -restricted edge-cut if each component of contains at least vertices. The -restricted edge connectivity of , denoted by , is defined as the minimum cardinality of all -restricted edge-cuts. Let , where denotes the set of edges of each having exactly one endpoint in . A graph is said to be -optimal if , and super- if every minimum -restricted edge-cut isolates a component of size exactly . In this paper, firstly, we give some relations among -optimal, -optimal and super- for . Then we present degree conditions for arbitrary, triangle-free and bipartite graphs to be -optimal and super-, respectively; moreover, we give some examples which prove that our results are the best possible. [Copyright &y& Elsevier]

Abstract: A -factor of a graph is a spanning subgraph of such that each component of is a path of order at least (). Akiyama et al. [J. Akiyama, D. Avis, H. Era, On a {1, 2}-factor of a graph, TRU Math. 16 (1980) 97–102] obtained a necessary and sufficient condition for a graph with a -factor. Kaneko [A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, J. Combin. Theory Ser. B 88 (2003) 195–218] gave a characterization of a graph with a -factor. We define the concept of a -factor covered graph, i.e. for each edge of , there is a -factor covering (). Based on these two results, we obtain respective necessary and sufficient conditions defining a -factor covered graph and a -factor covered graph. [Copyright &y& Elsevier]

Abstract: For a graph with the vertex set , we denote by the distance between vertices and in , by the degree of vertex . The Hosoya polynomial of is . The partial Hosoya polynomials of are for positive integer numbers and . It is shown that and for arbitrary catacondensed benzenoid graphs and with equal number of hexagons. As an application, we give an affine relationship between 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]. [Copyright &y& Elsevier]

Abstract: A graph that can be isometrically embedded into a hypercube is called a partial cube (or binary Hamming graph). Klavžar, Gutman and Mohar [S. Klavžar, I. Gutman, B. Mohar, Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inf. Comput. Sci. 35 (1995) 590–593] showed that all benzenoid systems are partial cubes. In this article we show that none of the coronoid systems (benzenoid systems with “holes”) is a partial cube. [Copyright &y& Elsevier]

Abstract: An induced subgraph of a graph is gated if for every vertex outside there exists a vertex inside such that each vertex of is connected with by a shortest path passing through . The gated amalgam of graphs and is obtained from and by identifying their isomorphic gated subgraphs and . Two theorems on Hosoya polynomials of gated amalgams are provided. As their applications, explicit expressions for Hosoya polynomials of hexagonal chains are obtained. [Copyright &y& Elsevier]

Abstract: In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with vertices and cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star and one vertex of degree of , we denote by the resulting graph. We show that the graph is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs. [Copyright &y& Elsevier]

For a connected graph G we denote by d(G,k) the number of vertex pairs at distance k. The Hosoya polynomial of G is H(G,x) = ∑k≥0d(G,k)xk. In this paper, analytical formulae for calculating the polynomials of armchair open-ended nanotubes are given. Furthermore, the Wiener index, derived from the first derivative of the Hosoya polynomial in x = 1, and the hyper-Wiener index, from one-half of the second derivative of the Hosoya polynomial multiplied by x in x = 1, can be calculated. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2007 [ABSTRACT FROM AUTHOR]

Abstract: An outerplane graph is a connected plane graph with all vertices lying on the boundary of its outer face. For a catacondensed benzenoid graph , i.e. a 2-connected outerplane graph each inner face of which is a regular hexagon, S. Klavžar and P. Žigert [A min–max result on catacondensed benzenoid graphs, Appl. Math. Lett. 15 (2002) 279–283] discovered that the smallest number of elementary cuts that cover equals the dimension of a largest induced hypercube of its resonance graph. In this note, we extend the result to any 2-connected outerplane bipartite graph by applying Dilworth’s min–max theorem on partially ordered sets. [Copyright &y& Elsevier]

The resistance distance rij between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices. In this work, closed-form formulae for Kirchhoff index and resistance distances of circulant graphs are derived in terms of Laplacian spectrum and eigenvectors. Special formulae are also given for four classes of circulant graphs (complete graphs, complete graphs minus a perfect matching, cycles, Möbius ladders Mp). In particular, the asymptotic behavior of Kf(Mp) as p → ∞ is obtained, that is, Kf(Mp) grows as 1/6p3 as p → ∞. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2007 [ABSTRACT FROM AUTHOR]

Abstract: A graph G is said to be bicritical if has a perfect matching for every choice of a pair of points and . Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G. [Copyright &y& Elsevier]

The Z-transformation graph of perfect matchings of a plane bipartite graph G has the perfect matchings of G as vertices, two perfect matchings being adjacent if their symmetric difference forms a cycle that is the boundary of an interior face of G. In this note, we prove that the Z-transformation graph of perfect matchings of an outerplane bipartite graph has a Hamilton path. [Copyright &y& Elsevier]

Let G be a plane bipartite graph with at least two perfect matchings. The Z-transformation graph, ZF(G), of G with respect to a specific set F of faces is defined as a graph on the perfect matchings of G such that two perfect matchings M1 and M2 are adjacent provided M1 and M2 differ only in a cycle that is the boundary of a face in F. If F is the set of all interior faces, ZF(G) is the usual Z-transformation graph; If F contains all faces of G it is a novel graph and called the total Z-transformation graph. In this paper, we give some simple characterizations for the Z-transformation graphs to be connected by applying the above new idea. Furthermore, we show that the total Z-transformation graph of G is 2-connected if G is elementary; the total Z-transformation digraph of G is strongly connected if and only if G is elementary. [Copyright &y& Elsevier]

Let G be a plane bipartite graph. The Z-transformation graph Z(G) and its orientation Z→(G) on the maximum matchings of G are defined. If G has a perfect matching, Z(G) and Z→(G) are the usual Z-transformation graph and digraph. If G has neither isolated vertices nor perfect matching, then Z(G) is not connected. This paper mainly shows that some basic results for Z-transformation graph (digraph) of a plane elementary bipartite graph still hold for every nontrivial component of Z(G) (Z→(G)). In particular, by obtaining a result that every shortest path of Z(G) from a source of Z→(G) corresponds to a directed path of Z→(G), we show that every nontrivial component of Z→(G) has exactly one source and one sink. Accordingly, it follows that the block graph of every nontrivial component of Z(G) is a path. In addition, we give a simple characterization for a maximum matching of G being a cut-vertex of Z(G). [Copyright &y& Elsevier]