Reconstructing a Graph from its Arc Incidence Graph

Introduced implicitly by Brualdi and Massey (Discret Math 122(1–3):51–58, 1993) in their work on the strong chromatic index of multigraphs, the arc incidence graph AI(G) of a graph G is defined as the square of the line graph of the incidence graph of G. We describe a linear-time algorithm for recognizing arc incidence graphs and reconstructing a graph with no isolated vertices from its arc incidence graph.     

图的线独立数的一个公式

本文中我们用等秩变换证明了连通图G的所有生成树的邻接矩阵的秩中最大者就是图G线独立数的两倍。特别,我们给出了连通图G具有完美匹配的一个新的充要条件。     

二部图生成树的新的计数公式(英文)

设G =(V ,U ,E)是一个连通的二部图 ,其中｜V｜=m ,｜U｜=n .令M (G)表示G的关联矩阵 ,Jk×s 表示元素全为 1的k ×s矩阵 ,R =M (G)M (G)′ , Jm n =Jm -Jm×n-Jn×m Jn,t(G)表示G中生成树的个数 .在本文中我们不用对G的边定向而获得了下面的主要结论 :t(G) =(m n) -2 det( Jm n R) .     

Construction of a Maximally Edge-Connected Graph with Prescribed Degrees

Let 〈d₁,d₂,...,d_p,〉 be a realizable degree sequence, d_i?2; then a graph G can be constructed so that deg(v_i and so that for i≠j, the number of edge-disjoint paths between v_i and v_j is (d_i,d_j).     

A Graph Theoretic Expansion Formula for Cluster Algebras of Classical Type

In this paper we give a graph theoretic combinatorial interpretation for the cluster variables that arise in most cluster algebras of finite type with bipartite seed. In particular, we provide a family of graphs such that a weighted enumeration of their perfect matchings encodes the numerator of the associated Laurent polynomial while decompositions of the graphs correspond to the denominator. This complements recent work by Schiffler and Carroll-Price for a cluster expansion formula for the A _n case while providing a novel interpretation for the B _n , C _n , and D _n cases.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

On the Maximum Matching Graph of a Graph

1IntroductionMatchingtheory,aswellastheassignmentprobleminlinearprogramming,hasawiderangeofapplicationinthetheoryandpracticeofoperationsresearch.Bysomepracticalmotivations,e.g.,forfindingalloptimalsolutions,peoplewanttoknowthestructurepropertiesofallmaximummatchingsofagraphG.InthecasethatGhasperfectmatchings,extensiveworkhasbeendoneontheso-calledperfectmatChinggrape(or1-factorgraph),inwhichtwoperfectmatchingsMIandMZaresaidtobeadjacentifMI~MZ@E(C)whereCisanMI-alternatingcycleofG.Therewer…     

用一个哲学公式理解级数的收敛

通过对林群的哲学公式(相对真理)/(绝对真理)=0.9的理解,对级数收敛,函数展成幂级数和周期函数展成傅里叶级数,用数据直观演示其哲学思想.     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.     

一个积和式计数公式的等价形式及其证明

给出了一个积和式计数公式在图论意义下的一般表达式 ,并证明了它们之间的等价关系     

Spanning Connectivity of the Power of a Graph and Hamilton-Connected Index of a Graph

Let G = (V, E) be a connected graph. The hamiltonian index h(G) (Hamilton-connected index hc(G)) of G is the least nonnegative integer k for which the iterated line graph L ^k (G) is hamiltonian (Hamilton-connected). In this paper we show the following. (a) If |V(G)| ≥ k + 1 ≥ 4, then in G ^k , for any pair of distinct vertices {u, v}, there exists k internally disjoint (u, v)-paths that contains all vertices of G; (b) for a tree T,  h(T) ≤ hc(T) ≤ h(T) + 1, and for a unicyclic graph G,  h(G) ≤ hc(G) ≤ max{h(G) + 1, k′ + 1}, where k′ is the length of a longest path with all vertices on the cycle such that the two ends of it are of degree at least 3 and all internal vertices are of degree 2; (c) we also characterize the trees and unicyclic graphs G for which hc(G) = h(G) + 1.     

Every 4-Connected Line Graph of a Planar Graph is Hamiltonian

Let G be a graph withE(G) $#x2260;ø. The line graph of G, written L(G) hasE(G) as its vertex set, where two vertices are adjacent in L(G) if and only if the corresponding edges are adjacent inG. Thomassen conjectured that all 4-connected line graphs are hamiltonian [2]. We show that this conjecture holds for planar graphs.     

Untangling a Planar Graph

A straight-line drawing δ of a planar graph G need not be plane but can be made so by untangling it, that is, by moving some of the vertices of G. Let shift(G,δ) denote the minimum number of vertices that need to be moved to untangle δ. We show that shift(G,δ) is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix(G,δ)=n?shift(G,δ) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling δ. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log\log n}$ vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ _G of G with $\ensuremath {\mathrm {fix}}(G,\delta_{G})\leq \sqrt{n-2}+1$ and an n-vertex outerplanar graph H and a drawing δ _H of H with $\ensuremath {\mathrm {fix}}(H,\delta_{H})\leq2\sqrt{n-1}+1$ . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.     

Color Chain of a Graph

For a simple connected undirected graph G, c(G), c_f(G), Y_f(G), f(G), ?G(G){\chi(G), \chi_f(G), \Psi_f(G), \phi(G), \partial \Gamma (G)} and Ψ(G) denote respectively the chromatic number, fall chromatic number (assuming that it exists for G), fall achromatic number, b-chromatic number, partial Grundy number and achromatic number of G. It is shown in Dunbar et al. (J Combin Math & Combin Comput 33:257–273, 2000) that for any graph G for which fall coloring exists, c(G) ￡ c_f(G) ￡ Y_f (G) ￡ f(G) ￡ ?G(G) ￡ Y(G){\chi (G)\leq \chi_f(G) \leq \Psi_f (G) \leq \phi(G) \leq \partial \Gamma (G)\leq \Psi (G)} . In this paper, we exhibit an infinite family of graphs G with a strictly increasing color chain: c(G) < c_f(G) < Y_f (G) < f(G) < ?G(G) < Y(G){\chi (G) < \chi_f(G) < \Psi_f (G) < \phi(G) < \partial \Gamma (G) < \Psi (G)} . The existence of such a chain was raised by Dunbar et al.     

Edge-Distinguishing Index of a Graph

We introduce a concept of edge-distinguishing colourings of graphs. A closed neighbourhood of an edge \({e\in E(G)}\) is a subgraph N[e] induced by e and all edges adjacent to it. We say that a colouring c : E(G) → C does not distinguish two edges e ₁ and e ₂ if there exists an isomorphism φ of N[e ₁] onto N[e ₂] such that φ(e ₁) = e ₂ and φ preserves colours of c. An edge-distinguishing index of a graph G is the minimum number of colours in a proper colouring which distinguishes every two distinct edges of G. We determine the edge-distinguishing index for cycles, paths and complete graphs.     

最大边数的Cordial图的构造

对于n阶Cordial图G，本给出G的边数的上确界e^*，并给出边数达到e^*的Cordial图的构造。     

带重结点的三角求积公式的迭代构造

本文以三角多项式类作为工具讨论了偶数个结点情况下的带重结点的具有最大三角精度的三角求积公式,由拟正交三角多项式的性质给出了求积公式系数的迭代构造。     

Forbidden Triples Containing a Complete Graph and a Complete Bipartite Graph of Small Order

For a graph G and a set \({\mathcal{F}}\) of connected graphs, G is said be \({\mathcal{F}}\) -free if G does not contain any member of \({\mathcal{F}}\) as an induced subgraph. We let \({\mathcal{G} _{3}(\mathcal{F})}\) denote the set of all 3-connected \({\mathcal{F}}\) -free graphs. This paper is concerned with sets \({\mathcal{F}}\) of connected graphs such that \({\mathcal{F}}\) contains no star, \({|\mathcal{F}|=3}\) and \({\mathcal{G}_{3}(\mathcal{F})}\) is finite. Among other results, we show that for a connected graph T( ≠ K ₁) which is not a star, \({\mathcal{G}_{3}(\{K_{4},K_{2,2},T\})}\) is finite if and only if T is a path of order at most 6.     

对一个不定积分公式的一点注记

探讨积分表中的一个不定积分,即∫dx/a^2cos^2x＋b^2sin^2x=1/abarctan（b/atan x）＋C的不严密性,并给出了该积分的严密表示形式．