Vertex-edge domination in graphs

In this paper we study graph parameters related to vertex-edge domination, where a vertex dominates the edges incident to it as well as the edges adjacent to these incident edges. First, we present new relationships relating the ve-domination to some other domination parameters, answering in the affirmative four open questions posed in the 2007 PhD thesis by Lewis. Then we provide an upper bound for the independent ve-domination number in terms of the ve-domination number for every nontrivial connected K_1,k-free graph, with k ≥ 3, and we show that the independent ve-domination number is bounded above by the domination number for every nontrivial tree. Finally, we establish an upper bound on the ve-domination number for connected C₅-free graphs, improving a recent bound given for trees.     

Dominating Cycles and Forbidden Pairs Containing $$P_{5}$$

A cycle C in a graph G is dominating if every edge of G is incident with at least one vertex of C. For a set \(\mathcal {H}\) of connected graphs, a graph G is said to be \(\mathcal {H}\)-free if G does not contain any member of \(\mathcal {H}\) as an induced subgraph. When \(|\mathcal {H}| = 2, \mathcal {H}\) is called a forbidden pair. In this paper, we investigate the characterization of the class of the forbidden pairs guaranteeing the existence of a dominating cycle and show the following two results: (i) Every 2-connected \(\{P_{5}, K_{4}^{-}\}\)-free graph contains a longest cycle which is a dominating cycle. (ii) Every 2-connected \(\{P_{5}, W^{*}\}\)-free graph contains a longest cycle which is a dominating cycle. Here \(P_{5}\) is the path of order \(5, K_{4}^{-}\) is the graph obtained from the complete graph of order 4 by removing one edge, and \(W^{*}\) is the graph obtained from two triangles and an edge by identifying one vertex in each.     

A Twelve Vertex Theorem for 3-Connected Claw-Free Graphs

The cyclability of a graph H, denoted by C(H), is the largest integer r such that H has a cycle through any r vertices. For a claw-free graph H, by Ryjá?ek (J Comb Theory Ser B 70:217–224, 1997) closure concept, there is a \(K_3\)-free graph G such that the closure \(cl(H)=L(G)\). In this note, we prove that for a 3-connected claw-free graph H with its closure \(cl(H)=L(G)\), \(C(H)\ge 12\) if and only if G can not be contracted to the Petersen graph in such a way that each vertex in P is obtained by contracting a nontrivial connected \(K_3\)-free subgraph. This is an improvement of the main result in Györi and Plummer (Stud Sci Math Hung 38:233–244, 2001).     

Every 3-connected $$\{K_{1,3},N_{1,2,3}\}$$-free graph is Hamilton-connected

A graph G is \(\{X,Y\}\)-free if it contains neither X nor Y as an induced subgraph. Pairs of connected graphs X, Y such that every 3-connected \(\{X,Y\}\)-free graph is Hamilton-connected have been investigated recently in (2002, 2000, 2012). In this paper, it is shown that every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected, where \(N_{1,2,3}\) is the graph obtained by identifying end vertices of three disjoint paths of lengths 1, 2, 3 to the vertices of a triangle.     

Tree-Like Structure Graphs with Full Diversity of Balls

Under study is the diversity of metric balls in connected finite ordinary graphs considered as a metric space with the usual shortest-path metric. We investigate the structure of graphs in which all balls of fixed radius i are distinct for each i less than the diameter of the graph. Let us refer to such graphs as graphs with full diversity of balls. For these graphs, we establish some properties connected with the existence of bottlenecks and find out the configuration of blocks in the graph. Using the obtained properties, we describe the tree-like structure graphs with full diversity of balls.     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

Edge-transitive products

This paper concerns finite, edge-transitive direct and strong products, as well as infinite weak Cartesian products. We prove that the direct product of two connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive and at least one is arc-transitive, or one factor is edge-transitive and the other is a complete graph with loops at each vertex. Also, a strong product is edge-transitive if and only if all factors are complete graphs. In addition, a connected, infinite non-trivial Cartesian product graph G is edge-transitive if and only if it is vertex-transitive and if G is a finite weak Cartesian power of a connected, edge- and vertex-transitive graph H, or if G is the weak Cartesian power of a connected, bipartite, edge-transitive graph H that is not vertex-transitive.     

On the extent of star countable spaces

For a topological property P, we say that a space X is star Pif for every open cover Uof the space X there exists Y ? X such that St(Y,U) = X and Y has P. We consider star countable and star Lindelöf spaces establishing, among other things, that there exists first countable pseudocompact spaces which are not star Lindelöf. We also describe some classes of spaces in which star countability is equivalent to countable extent and show that a star countable space with a dense σ-compact subspace can have arbitrary extent. It is proved that for any ω ₁-monolithic compact space X, if C _p (X)is star countable then it is Lindelöf.     

Enumeration of labeled outerplanar bicyclic and tricyclic graphs

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n.     

On the diameter of the intersection graph of a finite simple group

Let G be a finite group. The intersection graph Δ_G of G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of G, and two distinct vertices X and Y are adjacent if X ∩ Y ≠ 1, where 1 denotes the trivial subgroup of order 1. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters of intersection graphs of finite non-abelian simple groups have an upper bound 28. In particular, the intersection graph of a finite non-abelian simple group is connected.     

Quasirecognition by prime graph of <Emphasis Type="Italic">L</Emphasis><Subscript>10</Subscript>(2)

Let G be a finite group. The prime graph of G is denoted by Γ(G). The main result we prove is as follows: If G is a finite group such that Γ(G) = Γ(L ₁₀(2)) then G/O ₂(G) is isomorphic to L ₁₀(2). In fact we obtain the first example of a finite group with the connected prime graph which is quasirecognizable by its prime graph. As a consequence of this result we can give a new proof for the fact that the simple group L ₁₀(2) is uniquely determined by the set of its element orders.     

Free groups and ends of graphs

Let X be a connected graph. An automorphism of X is said to be parabolic if it leaves no finite subset of vertices in X invariant and fixes precisely one end of X and hyperbolic if it leaves no finite subset of vertices in X invariant and fixes precisely two ends of X. Various questions concerning dynamics of parabolic and hyperbolic automorphisms are discussed.The set of ends which are fixed by some hyperbolic element of a group G acting on X is denoted by ?(G). If G contains a hyperbolic automorphism of X and G fixes no end of X, then G contains a free subgroup F such that ?(F) is dense in ?(G) with respect to the natural topology on the ends of X.As an application we obtain the following: A group which acts transitively on a connected graph and fixes no end has a free subgroup whose directions are dense in the end boundary.     

Proper connection number of bipartite graphs

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.     

Some sufficient conditions for Hamiltonian property in terms of Wiener-type invariants

The Wiener-type invariants of a simple connected graph G = (V, E) can be expressed in terms of the quantities \(W_{f}=\sum_{\{u,v\}\subseteq V}f(d_{G}(u,v))\) for various choices of the function f(x), where d_G(u,v) is the distance between vertices u and v in G. In this paper, we give some sufficient conditions for a connected graph to be Hamiltonian, a connected graph to be traceable, and a connected bipartite graph to be Hamiltonian in terms of the Wiener-type invariants.     

Variations on a theorem of Arhangel’skii and Pytkeev

We identify continuous real-valued functions on a Tychonoff space X with their (closed) graphs thus allowing for C(X) to naturally inherit the lower Vietoris topology from the ambient hyperspace. We then calculate a bitopological version of tightness using the weak Lindelöf numbers of finite powers of X. We also characterize bitopological versions of countable fan and strong fan tightness of the point-open topology with respect to the lower Vietoris topology on C(X) in terms of suitable covering properties of the powers X ⁿ formulated using the language of S ₁ and S _fin selection principles.     

<Emphasis Type="Italic">C</Emphasis>*-Algebras Generated by Mappings. Criterion of Irreducibility

We study the operator algebra associated with a self-mapping ? on a countable set X which can be represented as a directed graph. The algebra is generated by the family of partial isometries acting on the corresponding l²(X). We study the structure of involutive semigroup multiplicatively generated by the family of partial isometries. We formulate the criterion when the algebra is irreducible on the Hilbert space. We consider the concrete examples of operator algebras. In particular, we give the examples of nonisomorphic C*-algebras, which are the extensions by compact operators of the algebra of continuous functions on the unit circle.     

On the local closure of clones on countable sets

We consider clones on countable sets. If such a clone has quasigroup operations, is locally closed and countable, then there is a function \({f : \mathbb{N} \rightarrow \mathbb{N}}\) such that the n-ary part of C is equal to the n-ary part of Pol \({{\rm Inv}^{[f(n)]} C}\), where \({{\rm Inv}^{[f(n)]} C}\) denotes the set of f(n)-ary invariant relations of C.     

When a line graph associated to annihilating-ideal graph of a lattice is planar or projective

Let (L,∧, ∨) be a finite lattice with a least element 0. AG(L) is an annihilating-ideal graph of L in which the vertex set is the set of all nontrivial ideals of L, and two distinct vertices I and J are adjacent if and only if I ∧ J = 0. We completely characterize all finite lattices L whose line graph associated to an annihilating-ideal graph, denoted by L(AG(L)), is a planar or projective graph.     

Atomic subspaces of {L_1}-martingale spaces

In Part I of the present paper the following problem was investigated. Let G be a finite simple graph, and S be a finite set of primes. We say that G is representable with S if it is possible to attach rational numbers to the vertices of G such that the vertices v₁, v₂ are connected by an edge if and only if the difference of the attached values is an S-unit. In Part I we gave several results concerning the representability of graphs in the above sense.