Constructing even radius tightly attached half-arc-transitive graphs of valency four

A finite graph X is half-arc-transitive if its automorphism group is transitive on vertices and edges, but not on arcs. When X is tetravalent, the automorphism group induces an orientation on the edges and a cycle of X is called an alternating cycle if its consecutive edges in the cycle have opposite orientations. All alternating cycles of X have the same length and half of this length is called the radius of X. The graph X is said to be tightly attached if any two adjacent alternating cycles intersect in the same number of vertices equal to the radius of X. Marušič (J. Comb. Theory B, 73, 41–76, 1998) classified odd radius tightly attached tetravalent half-arc-transitive graphs. In this paper, we classify the half-arc-transitive regular coverings of the complete bipartite graph K _4,4 whose covering transformation group is cyclic of prime-power order and whose fibre-preserving group contains a half-arc-transitive subgroup. As a result, two new infinite families of even radius tightly attached tetravalent half-arc-transitive graphs are constructed, introducing the first infinite families of tetravalent half-arc-transitive graphs of 2-power orders.      

A classification of tightly attached half-arc-transitive graphs of valency 4

A graph is said to be half-arc-transitive if its automorphism group acts transitively on the set of its vertices and edges but not on the set of its arcs. With each half-arc-transitive graph of valency 4 a collection of the so-called alternating cycles is associated, all of which have the same even length. Half of this length is called the radius of the graph in question. Moreover, any two adjacent alternating cycles have the same number of common vertices. If this number, the so-called attachment number, coincides with the radius, we say that the graph is tightly attached. In [D. Marušič, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B 73 (1998) 41–76], Marušič gave a classification of tightly attached half-arc-transitive graphs of valency 4 with odd radius. In this paper the even radius tightly attached graphs of valency 4 are classified, thus completing the classification of all tightly attached half-arc-transitive graphs of valency 4.     

On quartic half-arc-transitive metacirculants

Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1, n≥2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ ^m has at least one fixed vertex. A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. In this article quartic half-arc-transitive metacirculants are explored and their connection to the so called tightly attached quartic half-arc-transitive graphs is explored. It is shown that there are three essentially different possibilities for a quartic half-arc-transitive metacirculant which is not tightly attached to exist. These graphs are extensively studied and some infinite families of such graphs are constructed. Both authors were supported in part by “ARRS – Agencija za znanost Republike Slovenije”, program no. P1-0285.     

On the edge-binding number of some plane graphs

1. IntroductionSince WOodall gave out the concept of biIldi11g Ilu1lJber in 1973[l] ! the bil1ding nunlber fOrsome specia1 classes have beeIl studied by Kane and WaIlg Jianfang[']. Mirolawa Skowronskahave studied the binding number of Halin-graph[']. ZI1ang Zhongfu, Liu Li1lzhong andZhang Jianxun have extended the bil1di11g nuInber to the edges and studied tlle edge-bindingnumber of path, cycle, coInplete grapl1. I1l this paper, we study the edge-binding number ofouter plane graph, Ha…     

On the classification of quartic half-arc-transitive metacirculants

A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1 and n≥2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ^m has at least one fixed vertex. In a recent paper Maruši? and the author showed that each connected quartic half-arc-transitive metacirculant belongs to one (or possibly more) of four classes of such graphs, reflecting the structure of the quotient graph relative to the semiregular automorphism ρ. One of these classes coincides with the class of the so-called tightly-attached graphs, which have already been completely classified. In this paper a complete classification of the second of these classes, that is the class of quartic half-arc-transitive metacirculants for which the quotient graph relative to the semiregular automorphism ρ is a cycle with a loop at each vertex, is given.     

An infinite family of tetravalent half-arc-transitive graphs

A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, a new infinite family of tetravalent half-arc-transitive graphs with girth 4 is constructed, each of which has order 16m such that m>1 is a divisor of 2t²+2t+1 for a positive integer t and is tightly attached with attachment number 4m. The smallest graph in the family has order 80.     

On the oriented chromatic number of graphs with given excess

The excess of a graph G is defined as the minimum number of edges that must be deleted from G in order to get a forest. We prove that every graph with excess at most k has chromatic number at most and that this bound is tight. Moreover, we prove that the oriented chromatic number of any graph with excess k is at most k+3, except for graphs having excess 1 and containing a directed cycle on 5 vertices which have oriented chromatic number 5. This bound is tight for k?4.     

Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.     

最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.     

Packing edge-disjoint cycles in graphs and the cyclomatic number

For a graph G let μ(G) denote the cyclomatic number and let ν(G) denote the maximum number of edge-disjoint cycles of G.We prove that for every k≥0 there is a finite set P(k) such that every 2-connected graph G for which μ(G)−ν(G)=k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k≤2 exactly.     

Toll number of the Cartesian and the lexicographic product of graphs

Toll convexity is a variation of the so-called interval convexity. A tolled walk $T$ between two non-adjacent vertices $u$ and $v$ in a graph $G$ is a walk, in which $u$ is adjacent only to the second vertex of $T$ and $v$ is adjacent only to the second-to-last vertex of $T$. A toll interval between $u,v\in V\left(G\right)$ is a set $T_G(u,v)=\{x\in V\left(G\right):x\text{ lies on a tolled walk between }u\text{ and }v\}$. A set $S?V\left(G\right)$ is toll convex, if $T_G(u,v)?S$ for all $u,v\in S$. A toll closure of a set $S?V\left(G\right)$ is the union of toll intervals between all pairs of vertices from $S$. The size of a smallest set $S$ whose toll closure is the whole vertex set is called a toll number of a graph $G$, $tn\left(G\right)$. The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if $H$ is not isomorphic to a complete graph, $tn(G°H)\le 3?tn\left(G\right)$. We give some necessary and sufficient conditions for $tn(G°H)=3?tn\left(G\right)$. Moreover, if $G$ has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with $tn(G°H)=2$ are characterized. Finally, the formula for $tn(G°H)$ is given — it is described in terms of the so-called toll-dominating triples or, if $H$ is complete, toll-dominating pairs.     

On the b-chromatic number of Kneser graphs

In this note, we prove that for any integer n≥3 the b-chromatic number of the Kneser graph KG(m,n) is greater than or equal to . This gives an affirmative answer to a conjecture of [6].     

Independence number of products of Kneser graphs

We study the independence number of a product of Kneser graph $K(n,k)$ with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for $\alpha (K(n,k)⊠K(n,k))$ is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of $K(n,2)\square K(n,2)$, which are asymptotically tending to $n^3∕3$ and $3n^3∕8$, respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the $\ell$-independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs $K(2k+1,k)$, which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the $s$-stable Kneser graphs $K{(ks+1,k)}_{s-stab}$, derive a formula for their $\ell$-independence number, and give the exact value of the independence number of the Cartesian square of $K{(ks+1,k)}_{s-stab}$.     

On the b-continuity property of graphs

This paper deals with b-colorings of a graph G, that is, proper colorings in which for each color c, there exists at least one vertex colored by c such that its neighbors are colored by each other color. The b-chromatic numberb(G) of a graph G is the maximum number of colors for which G has a b-coloring. It is easy to see that every graph G has a b-coloring using χ(G) colors.We say that G is b-continuous iff for each k, χ(G)?k?b(G), there exists a b-coloring with k colors. It is well known that not all graphs are b-continuous. We call b-spectrumS_b(G) of G to be the set of integers k for which there is a b-coloring of G by k colors. We show that for any finite integer set I, there exists a graph whose b-spectrum is I and we investigate the complexity of the problem of deciding whether a graph G is b-continuous, even if b-colorings using χ(G) and b(G) colors are given.     

On Harary index of graphs

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph G=(V,E) and two nonadjacent vertices v_i and v_j in V(G) of G, recall that G+v_iv_j is the supergraph formed from G by adding an edge between vertices v_i and v_j. Denote the Harary index of G and G+v_iv_j by H(G) and H(G+v_iv_j), respectively. We obtain lower and upper bounds on H(G+v_iv_j)−H(G), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained.