Search

A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A path P in a total-colored graph G is called a total-proper path if (1) any two adjacent edges of P are assigned distinct colors; (2) any two adjacent internal vertices of P are assigned distinct colors; and (3) any internal vertex of P is assigned a distinct color from its incident edges of P. The total-colored graph G is total-proper connected if any two distinct vertices of G are connected by a total-proper path. The total-proper connection number of a connected graph G, denoted by tpc(G), is the minimum number of colors that are required to make G total-proper connected. In this paper, we first characterize the graphs G on n vertices with tpc(G)=n-1. Based on this, we obtain a Nordhaus-Gaddum-type result for total-proper connection number. We prove that if G and G¯ are connected complementary graphs on n vertices, then 6≤tpc(G)+tpc(G¯)≤n+2. Examples are given to show that the lower bound is sharp for n≥4. The upper bound is reached for n≥4 if and only if G or G¯ is the tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

The atom-bond connectivity (ABC) index of a graph G is defined to be $$ABC(G)=\sum _{uv\in E(G)}\sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}}$$ where d( u) is the degree of a vertex u. The ABC index plays a key role in correlating the physical-chemical properties and the molecular structures of some families of compounds. In this paper, we describe the structural properties of graphs which have the minimum ABC index among all connected graphs with a given degree sequence. Moreover, these results are used to characterize the extremal graphs which have the minimum ABC index among all unicyclic and bicyclic graphs with a given degree sequence. [ABSTRACT FROM AUTHOR]

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d≥2.⌈k/2⌉. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d≥2k-1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2.⌈k/2⌉ (for k-edge-connectivity) or 2k-1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is A P X-hard. [ABSTRACT FROM AUTHOR]

We consider the contact process on finite and connected graphs and study the behavior of the extinction time, that is, the amount of time that it takes for the infection to disappear in the process started from full occupancy. We prove, without any restriction on the graph G, that if the infection rate $$\lambda $$ is larger than the critical rate of the one-dimensional process, then the extinction time grows faster than $$\exp \{|G|/(\log |G|)^\kappa \}$$ for any constant $$\kappa > 1$$ , where | G| denotes the number of vertices of G. Also for general graphs, we show that the extinction time divided by its expectation converges in distribution, as the number of vertices tends to infinity, to the exponential distribution with parameter 1. These results complement earlier work of Mountford, Mourrat, Valesin and Yao, in which only graphs of bounded degrees were considered, and the extinction time was shown to grow exponentially in n; here we also provide a simpler proof of this fact. [ABSTRACT FROM AUTHOR]

Let D be a digraph on $\{v_{1},\ldots, v_{n}\}$ . Then the sequence $\{ (d^{+}(v_{1}), d^{-}(v_{1})), \ldots, (d^{+}(v_{n}), d^{-}(v_{n}))\}$ is called the degree sequence of D. For any given sequence of pairs of integers $\mathbf{d}=\{(d_{1}^{+}, d_{1}^{-}), \ldots, (d_{n}^{+}, d_{n}^{-})\}$ , if there exists a k-arc strongly connected digraph D such that d is the degree sequence of D, then d is realizable and D is a realization of d. In this paper, characterizations for k-arc-connected realizable sequences and realizable sequences with arc-connectivity exactly k are given. [ABSTRACT FROM AUTHOR]

In this paper, we determine the unique graph whose least signless Laplacian eigenvalue attains the minimum among all non-bipartite unicyclic graphs of order n with maximum degree Δ and among all non-bipartite connected graphs of order n with maximum degree Δ, respectively. [ABSTRACT FROM AUTHOR]

For an integer $$k$$ with $$k \ge 2$$ , a $$k$$ - tree (resp. a $$k$$ - forest) is a tree (resp. forest) with maximum degree at most $$k$$ . In this paper, we show that for any integer $$k$$ with $$k \ge 3$$ , any connected $$K_{1,k+1}$$ -free graph has a spanning $$k$$ -tree or a spanning $$k$$ -forest with only large components. [ABSTRACT FROM AUTHOR]

A parity subgraph of a graph is a spanning subgraph such that the degrees of all vertices have the same parity in both the subgraph and the original graph. Let $$G$$ be a cyclically 6-edge-connected cubic graph. Steffen (Intersecting 1-factors and nowhere-zero 5-flows , ) proved that $$G$$ has a nowhere-zero 5-flow if $$G$$ has two perfect matchings with at most two intersections. In this paper, we show that $$G$$ has a nowhere-zero 5-flow if $$G$$ has two parity subgraphs with at most two common edges, which generalizes Steffen's result. [ABSTRACT FROM AUTHOR]

Is it proves that every connected graph with s vertices of degree 1 and 3 anf t vertices of degree at least 4 has a spanning tree with at least $ \frac{1}{3}t + \frac{1}{4}s + \frac{3}{2} $ leaves. Infinite series of grpahs showing that our bound is tight are given. [ABSTRACT FROM AUTHOR]

Let D be a strongly connected digraph on n ≥ 4 vertices. A vertex v of D is noncritical if the digraph D − v is strongly connected. It is proved that if the sum of degrees of any two adjacent vertices of D is at least n + 1, then there exists a noncritical vertex in D, and if the sum of degrees of any two adjacent vertices of D is at least n + 2, then there exist two noncritical vertices in D. A series of examples confirms that these bounds are tight. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

It is proved that every connected graph with s vertices of degree 3 and t vertices of degree at least 4 has a spanning tree with $ \frac{2}{5}t+\frac{1}{5}s+\alpha $ leaves, where $ \alpha \geq \frac{8}{5} $. Moreover, α ≥ 2 for all graphs, except for three exclusions. All exclusions are regular graphs of degree 4, and they are explicitly described in the paper. An infinite series of graphs containing only vertices of degree 3 and 4, for which the maximal number of leaves in a spanning tree is equal to $ \frac{2}{5}t+\frac{1}{5}s+2 $, is presented. Therefore it is proved that the bound is tight. Bibliography: 12 titles. [ABSTRACT FROM AUTHOR]

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O( n). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O( n log n), where every intermediate triangulation has maximum degree at most k + 4. [ABSTRACT FROM AUTHOR]

Let G be a graph. We denote p( G) and c( G) the order of a longest path and the order of a longest cycle of G, respectively. Let κ( G) be the connectivity of G, and let σ( G) be the minimum degree sum of an independent set of three vertices in G. In this paper, we prove that if G is a 2-connected graph with p( G) − c( G) ≥ 2, then either (i) c( G) ≥ σ( G) − 3 or (ii) κ( G) = 2 and p( G) ≥ σ( G) − 1. This result implies several known results as corollaries and gives a new lower bound of the circumference. [ABSTRACT FROM AUTHOR]

An important property of a scale-free network which allows one to communicate between its nodes is the connectivity. From the simulation results it is known that such networks are resistant to random damage. It is also known from experiments that usually disconnecting such a graph is obtained by isolating a vertex. In this paper, we deal with a problem of isolating a vertex both experimentally and theoretically. For the theoretical results, we use the LCD model defined by Bollobás and Riordan. Among others, we prove that even after random deleting of n vertices ( m edges) for α < ( d − 1) /d, where d is the out-degree, with high probability, there are no isolated vertices in the remaining graph. [ABSTRACT FROM AUTHOR]