Vertex-Distinguishing Edge Colorings of Graphs with Degree Sum Conditions

An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c￠_vd(G){\chi'_{vd}(G)}. It is proved that c￠_vd(G) ￡ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and s₂(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ ₂(G) denotes the minimum degree sum of two nonadjacent vertices in G.     

Pan-H-Linked Graphs

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n ₀(H) isolated vertices and n ₁(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H^*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H^*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp.     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

Lower Bound of the Number of Maximum Genus Embeddings and Genus Embeddings of K 12s+7

In this paper, we study lower bound of the number of maximum orientable genus embeddings (or MGE in short) for a loopless graph. We show that a connected loopless graph of order n has at least \frac14^g_M(G)?_{v ? V(G)}(d(v)-1)!{\frac{1}{4^{\gamma_M(G)}}\prod_{v\in{V(G)}}{(d(v)-1)!}} distinct MGE’s, where γ _M (G) is the maximum orientable genus of G. Infinitely many examples show that this bound is sharp (i.e., best possible) for some types of graphs. Compared with a lower bound of Stahl (Eur J Combin 13:119–126, 1991) which concerns upper-embeddable graphs (i.e., embedded graphs with at most two facial walks), this result is more general and effective in the case of (sparse) graphs permitting relative small-degree vertices. We also obtain a similar formula for maximum nonorientable genus embeddings for general graphs. If we apply our orientable results to the current graph G _s of K _12s+7, then G _s has at least 2^3s distinct MGE’s.This implies that K _12s+7 has at least (22) ^s nonisomorphic cyclic oriented triangular embeddings for sufficient large s.     

The Edge Correlation of Random Forests

The conjecture was made by Kahn that a spanning forest F chosen uniformly at random from all forests of any finite graph G has the edge-negative association property. If true, the conjecture would mean that given any two edges ε₁ and ε₂ in G, the inequality \mathbbP(e₁ ? F, e₂ ? F) ￡ \mathbbP(e₁ ? F)\mathbbP(e₂ ? F){{\mathbb{P}(\varepsilon_{1} \in \mathbf{F}, \varepsilon_{2} \in \mathbf{F}) \leq \mathbb{P}(\varepsilon_{1} \in \mathbf{F})\mathbb{P}(\varepsilon_{2} \in \mathbf{F})}} would hold. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices. We derive explicit related results for random trees.     

Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs

Connected Domination Number of a Graph and its Complement

A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number γ _c (G) is the minimum size of such a set. Let d^*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ d^*(G)+4-(g_c(G)-3)(g_c([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that g_c(G)+g_c([`(G)]) ￡ d<sup>*</sup>(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when g<sub>c</sub>(G),g<sub>c</sub>([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that g_c(G)g_c([`(G)]) ￡ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

Cleaning Random d-Regular Graphs with Brooms

A model for cleaning a graph with brushes was recently introduced. Let α = (v ₁, v ₂, . . . , v _n ) be a permutation of the vertices of G; for each vertex v _i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N^-(v_i)={j: v_j v_i ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let b_a(G)=?_i=1ⁿ max{|N⁺(v_i)|-|N^-(v_i)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max _α b _α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

Proof of a conjecture of V. Nikiforov

Using analytical tools, we prove that for any simple graph G on n vertices and its complement [`(G)]\bar G the inequality $\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1$\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1 holds, where μ(G) and m( [`(G)] )\mu \left( {\bar G} \right) denote the greatest eigenvalue of adjacency matrix of the graphs G and [`(G)]\bar G respectively.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

Pairs of Disjoint Dominating Sets in Connected Cubic Graphs

For a connected cubic graph G of order n, we prove the existence of two disjoint dominating sets D ₁ and D ₂ with |D₁|+|D₂| ￡ \frac157198n+\frac89{|D_1|+|D_2|\leq \frac{157}{198}n+\frac{8}{9}}.     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

Ordering the non-starlike trees with large reverse wiener indices

The reverse Wiener index of a connected graph G is defined as {

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.