Arbitrarily traceable graphs and digraphs

The work in this paper extends and generalizes earlier work by Ore on arbitrarily traceable Euler graphs, by Harary on arbitrarily traceable digraphs, by Chartrand and White on randomly n-traversable graphs, and by Chartrand and Lick on randomly Eulerian digraphs. Arbitrarily traceable graphs of mixed type are defined and characterized in terms of a class of forbidden graphs. Arbitrarily traceable digraphs of mixed type are also defined and a simply applied characterization is given for them.     

Uncountable graphs with all their vertices in one face

Summary In 1967, Chartrand and Harary characterized finite outer-planar graphs, and Wagner studied uncountable graphs admitting a planar embedding. We continue this research for those outer-S graphs in surfaces S by studying uncountable graphs admitting S-embeddings with all their vertices in the same face (namely, outer-S embeddings).     

三圈图的Harary指数

图G的Harary指数是指图G中所有顶点对间的距离倒数之和. 三圈图是指边数等于顶点数加2的连通图. 研究了三圈图的Harary数, 给出了所有三圈图中具有极大Harary指数的图的结构以及含有三个圈的三圈图中具有次大Harary指数的图的结构.     

New types of integral sum graphs

Harary (Discrete Math. 124(1–3) (1994) 99) introduced the intergral sum graphs, and proved that the path P_n and matching mK₂ are integer sum graphs, and offered some conjectures. In this paper we enlarge the types of integral sum graphs. We prove that some caterpillars and mP_n are integral sum graphs and some conjectures of Harary are wrong.     

A characterization of α-outerplanar graphs

Chartrand and Harary have shown that if G is a non-outerplanar graph such that, for every edge e, both the deletion G\e and the contraction G/e of e from G are outerplanar, then G is isomorphic to K₄ or K_2,3. An α-outerplanar graph is a graph which is not outerplanar such that, for some edge α, both G\α and G/α are outerplanar. We describe various results for the class of α-outerplanar graphs and obtain a characterization of the class. © 1996 John Wiley & Sons, Inc.     

Zagreb,Harary and hyper-Wiener indices of graphs with a given matching number

In this paper, we present sharp bounds for the Zagreb indices, Harary index and hyper-Wiener index of graphs with a given matching number, and we also completely determine the extremal graphs.     

Split Permutation Graphs

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.     

On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.     

ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION

In this paper,we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn,a class of cubic convex polytopes considering the open problem raised in [M.Imran et al.,families of plane graphs with constant metric dimension,Utilitas Math.,in press] and finally Harary graphs H 5,n by partially answering to an open problem proposed in [I.Javaid et al.,Families of regular graphs with constant metric dimension,Utilitas Math.,2012,88:43-57].We prove that these classes of regular graphs have constant metric dimension.     

Edge Partition of Graphs Embeddable in the Projective Plane and the Klein Bottle

In a previous paper by the author joint with Baogang XU published in Discrete Math in 2018, we show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This edge partition then implies some results in thickness and outerthickness of toroidal graphs. In particular, if each planar graph has outerthickness at most $2$ (conjectured by Chartrand, Geller and Hedetniemi in 1971 and the confirmation of the conjecture was announced by Gon\c{c}alves in 2005), then the outerthickness of toroidal graphs is at most 3 which is the best possible due to $K_7$. In this paper we continue to study the edge partition for projective planar graphs and Klein bottle embeddable graphs. We show that (1) every non-planar but projective planar graph can be edge partitioned into a planar graph and a union of caterpillar trees; and (2) every non-planar Klein bottle embeddable graph can be edge partitioned into a planar graph and a subgraph of two vertex amalgamation of a caterpillar tree with a cycle with pendant edges. As consequences, the thinkness of projective planar graphs and Klein bottle embeddabe graphs are at most $2$, which are the best possible, and the outerthickness of these graphs are at most $3$.     

A characterization of consistent marked graphs

A marked graph is obtained from a graph by giving each point either a positive or a negative sign. Beineke and Harary raised the problem of characterzing consistent marked graphs in which the product of the signs of the points is positive for every cycle. In this paper a characterization is given in terms of fundamental cycles of a cycle basis.     

More on the Harary index of cacti

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. A cactus is a connected graph in which two cycles have at most one vertex in common. In this paper, we first determine graphs with the largest Harary index among all the cacti with n vertices and a perfect matching. Then we characterize the cacti with given order, cut edges and maximum Harary index. Finally, we establish upper bounds for Harary index among all cacti with n vertices and k pendant vertices.     

Ascending Subgraph Decompositions in Oriented Complete Balanced Tripartite Graphs

In 1987, Alavi, Boals, Chartrand, Erdös, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). Though different classes of graphs have been shown to have an ASD, the conjecture remains open. In this paper we investigate the similar problem for digraphs. In particular, we will show that any orientation of a compete balanced tripartite graph has an ASD.     

连通的三重Kn-残差图

Erds P,Harary F和Klawe M研究了Kn-残差图,并对连通的m-Kn-残差图提出了一些结论和猜想．利用容斥原理以及集合的运算性质等方法,研究了连通的3-Kn-残差图,得到当顶点最小度为n时,3-Kn-残差图最小阶的计算公式以及相应的唯一极图．当n=2时,得到最小阶为ll以及相应的极图;当n=3时,得到最小阶为20并找到两个不同构的极图,不满足Erdos等提出的结论;当n=4时,得到最小阶为22及相应的极图;当n=8时,可以找到两个不同构的3-Kn-残差图,不满足Erdos等提出的结论;最后证明了当n=9,10时,最小阶分别为48和52以及相应的唯一极图,验证了Erdos等在文献（Residually-complete graphs[J]．Annals of Discrete Mathematics,1980,6：117．123）中提出的结论．     

On oriented 2-factorable graphs

Oriented 2-factorable graphs are reduced to bouquets by permutation voltage assignment in this paper. Introducing the concept ofk-class index of a permutation group, various oriented 2-factorable graphs are enumerated in this paper.     

Comment on “The Steiner number of a graph” by G. Chartrand and P. Zhang: [Discrete Mathematics 242 (2002) 41–54]

We show by counterexample that one of the main results in the paper “The Steiner number of a graph” by Chartrand and Zhang (Disc. Math. 242 (2002) 41–54) does not hold. To be more precise, we prove both that not every Steiner set is a geodetic set and that there are connected graphs whose Steiner number is strictly lower than its geodetic number.     

素数立方阶群局部传递的图

目的是研究局部传递图的性质和分类.运用置换群和陪集图的理论,获得了关于素数立方阶群局部传递图的完全分类,证明了这些图是一些互不相交的关于素数立方阶群边传递图的并.     

Minimum Size of n-Factor-Critical Graphs and k-Extendable Graphs

We determine the minimum size of n-factor-critical graphs and that of k-extendable bipartite graphs, by considering Harary graphs and related graphs. Moreover, we determine the minimum size of k-extendable non-bipartite graphs for k = 1, 2, and pose a related conjecture for general k.     

Diagonally neighbour transitive codes and frequency permutation arrays

Constant composition codes have been proposed as suitable coding schemes to solve the narrow band and impulse noise problems associated with powerline communication, while at the same time maintaining a constant power output. In particular, a certain class of constant composition codes called frequency permutation arrays have been suggested as ideal, in some sense, for these purposes. In this paper we characterise a family of neighbour transitive codes in Hamming graphs in which frequency permutation arrays play a central rode. We also classify all the permutation codes generated by groups in this family.     

Efficient open domination in Cayley graphs

Efficient open dominating sets in bipartite Cayley graphs are characterized in terms of covering projections. Necessary and sufficient conditions for the existence of efficient open dominating sets in certain circulant Harary graphs are given. Chains of efficient dominating sets, and of efficient open dominating sets, in families of circulant graphs are described as an application.