The Edge Rotation Graph

Let P be a set of n points on the plane in general position, n ≥  3. The edge rotation graph ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ , such as its connectivity and diameter. We show that if the vertices of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ are not triangulations of P, then it is connected and has diameter O(n ²). We also show that the chromatic number of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs.     

The Linear t-Colorings of Sierpiński-Like Graphs

A proper t-coloring of a graph G is a mapping ${\varphi: V(G) \rightarrow [1, t]}$ such that ${\varphi(u) \neq \varphi(v)}$ if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by ${\chi(G)}$ , is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by ${lc(G)}$ , is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S(n, k), ${S^+(n, k)}$ and ${S^{++}(n, k)}$ are studied. It is obtained that ${lc(S(n, k))= \chi (S(n, k)) = k}$ for any positive integers n and k, ${lc(S^+(n, k)) = \chi(S^+(n, k)) = k}$ and ${lc(S^{++}(n, k)) = \chi(S^{++}(n, k)) = k}$ for any positive integers ${n \geq 2}$ and ${k \geq 3}$ . Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely.     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

The Signed k-Submatchings in Graphs

A signed k-submatching of a graph G is a function f : E(G) → {?1,1} satisfying f (E _G (v)) ≤ 1 for at least k vertices ${v \in V(G)}$ . The maximum of the values of f (E(G)), taken over all signed k-submatchings f, is called the signed k-submatching number and is denoted by ${\beta_S^{k}(G)}$ . In this paper, sharp bounds on ${\beta_S^{k}(G)}$ for general graphs are presented. Exact values of ${\beta_S^{k}(G)}$ for several classes of graphs are found.     

Domination in Bipartite Graphs and in Their Complements

The domatic numbers of a graph G and of its complement $\bar G$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs G having $d\left( G \right) = d\left( {\bar G} \right)$ Further, we will present a partial solution to the problem: Is it true that if G is a graph satisfying $d\left( G \right) = d\left( {\bar G} \right)$ then $\gamma \left( G \right) = \gamma \left( {\bar G} \right)$ ? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement     

Independence number and minimum degree for fractional ID-k-factor-critical graphs

Let k be an integer with k?≥?1, and let G be a graph. A k-factor of G is a spanning subgraph F of G such that d _F (x)?=?k for each ${x\in V(G)}$ . Let ${h:E(G)\rightarrow[0,1]}$ be a function. If ${\sum_{e\ni x}h(e)=k}$ holds for each ${x\in V(G)}$ , then we call G[F _h ] a fractional k-factor of G with indicator function h, where ${F_h=\{e\in E(G): h(e) >0 \}}$ . A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical) if G?I has a fractional k-factor for every independent set I of G. In this paper, we prove that if ${\alpha(G)\leq\frac{4k(\delta(G)-k+1)}{k^{2}+6k+1}}$ , then G is fractional ID-k-factor-critical. The result is best possible in some sense.     

Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let ${c_{\infty}(G)}$ denote the number of cops needed to capture the robber in a graph G in this variant. We characterize graphs G with c _??(G) =? 1, and give an ${O( \mid V(G)\mid^2)}$ algorithm for their detection. We prove a lower bound for c _?? of expander graphs, and use it to prove three things. The first is that if ${np \geq 4.2 {\rm log}n}$ then the random graph ${G= \mathcal{G}(n, p)}$ asymptotically almost surely has ${\eta_{1}/p \leq \eta_{2}{\rm log}(np)/p}$ , for suitable positive constants ${\eta_{1}}$ and ${\eta_{2}}$ . The second is that a fixed-degree random regular graph G with n vertices asymptotically almost surely has ${c_{\infty}(G) = \Theta(n)}$ . The third is that if G is a Cartesian product of m paths, then ${n/4km^2 \leq c_{\infty}(G) \leq n/k}$ , where ${n = \mid V(G)\mid}$ and k is the number of vertices of the longest path.     

On topological diversity of rectilinear representations of countably infinite graphs

We prove that, for each simple graph G whose set of vertices is countably infinite, there is a family ${\varvec{\mathcal{R}}(\varvec{G})}$ of the cardinality of the continuum of graphs such that (1) each graph ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ is isomorphic to G, all vertices of H are points of the Euclidean space E ³, all edges of H are straight line segments (the ends of each edge are the vertices joined by it), the intersection of any two edges of H is either their common vertex or empty, and any isolated vertex of H does not belong to any edge of H; (2) all sets ${\varvec{\mathcal{B}}(\varvec{H})}$ ( ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ ), where ${\varvec{\mathcal{B}}(\varvec{H})\subset \mathbf{E}^3}$ is the union of all vertices and all edges of H, are pairwise not homeomorphic; moreover, for any graphs ${\varvec{H}_1 \in \varvec{\mathcal{R}}(\varvec{G})}$ and ${\varvec{H}_2 \in \varvec{\mathcal{R}}(\varvec{G})}$ , ${\varvec{H}_1 \ne \varvec{H}_2}$ , and for any finite subsets ${\varvec{S}_i \subset \varvec{\mathcal{B}}(\varvec{H}_i)}$ (i = 1, 2), the sets ${\varvec{\mathcal{B}}(\varvec{H}_1){\setminus} \varvec{S}_1}$ and ${\varvec{\mathcal{B}}(\varvec{H}_2){\setminus} \varvec{S}_2}$ are not homeomorphic.     

On the Broadcast Independence Number of Grid Graph

A broadcast on a nontrivial connected graph G is a function ${f:V \longrightarrow \{0, \ldots,\operatorname{diam}(G)\}}$ such that for every vertex ${v \in V(G)}$ , ${f(v) \leq e(v)}$ , where ${\operatorname{diam}(G)}$ denotes the diameter of G and e(v) denotes the eccentricity of vertex v. The broadcast independence number is the maximum value of ${\sum_{v \in V} f(v)}$ over all broadcasts f that satisfy ${d(u,v) > \max \{f(u), f(v)\}}$ for every pair of distinct vertices u, v with positive values. We determine this invariant for grid graphs ${G_{m,n} = P_m \square P_n}$ , where ${2 \leq m \leq n}$ and □ denotes the Cartesian product. We hereby answer one of the open problems raised by Dunbar et al. in (Discrete Appl Math 154:59–75, 2006).     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

Degree Sum Conditions for Hamiltonicity on k-Partite Graphs

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least \(\frac{p} {2}\) then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than \(\frac{p} {4}\) then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian.     

b-Chromatic Number of Cartesian Product of Some Families of Graphs

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. It is known that for any two graphs G and H, ${b(G \square H) \geq {\rm {max}} \{b(G), b(H)\}}$ , where ${\square}$ stands for the Cartesian product. In this paper, we determine some families of graphs G and H for which strict inequality holds. More precisely, we show that for these graphs G and H, ${b(G \square H) \geq b(G) + b(H) - 1}$ . This generalizes one of the results due to Kouider and Mahéo.     

Extremal Zagreb Indices of Graphs with a Given Number of Cut Edges

For a graph, the first Zagreb index M ₁ is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M ₂ is equal to the sum of the products of the degrees of pairs of adjacent vertices. Denote by ${\mathcal{G}_{n,k}}$ the set of graphs with n vertices and k cut edges. In this paper, we showed the types of graphs with the largest and the second largest M ₁ and M ₂ among ${\mathcal{G}_{n,k}}$ .     

A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture

The article shrinks the Δ = 6 hole that exists in the family of planar graphs which satisfy the total coloring conjecture. Let G be a planar graph. If ${v_n^k}$ represents the number of vertices of degree n which lie on k distinct 3-cycles, for ${n, k \in \mathbb{N}}$ , then the conjecture is true for planar graphs which satisfy ${v_5^4 +2(v_5^{5^+} +v_6^4) +3v_6^5 +4v_6^{6^+} < 24}$ .     

Endpoint bounds for an analytic family of maximal functions

In this paper,for the plane curve T=.we define an analytic family of maximal functions asso-ciated to T asM_2f(λ)=sup_n>oh~-1∫_R相似文献   

An extremal problem in graph theory

It is proved that the maximum number of cut-vertices in a connected graph withn vertices andm edges is $$max\left\{ {q:m \leqq (_2^{n - q} ) + q} \right\}$$ All the extremal graphs are determined and the corresponding problem for cut-edges is also solved.     

More on monochromatic-rainbow Ramsey type theorems

An edge colored graph is called a rainbow if no two of its edges have the same color. Let ? and $\mathcal{G}$ be two families of graphs. Denote by $RM({\mathcal{H}},\mathcal{G})$ the smallest integer R, if it exists, having the property that every coloring of the edges of K _R by an arbitrary number of colors implies that either there is a monochromatic subgraph of K _R that is isomorphic to a graph in ? or there is a rainbow subgraph of K _R that is isomorphic to a graph in $\mathcal{G}$ . ${\mathcal{T}}_{n}$ is the set of all trees on n vertices. ${\mathcal{T}}_{n}(k)$ denotes all trees on n vertices with diam(T _n (k))≤k. In this paper, we investigate $RM({\mathcal{T}}_{n},4K_{2})$ , $RM({\mathcal{T}}_{n},K_{1,4})$ and $RM({\mathcal{T}}_{n}(4),K_{3})$ .     

Two Forbidden Subgraph Pairs for Hamiltonicity of 3-Connected Graphs

For integers i, j, k with ${i\geq j\geq k\geq 0}$ , let N _{i, j, k} be the graph obtained by identifying end vertices of three disjoint paths of lengths i, j, k to the vertices of a triangle. In this paper, we show that every 3-connected {K _1,3, N _{i, 7-i, 2}}-free graph is hamiltonian, where ${i \in \{4,5\}}$ . This result is sharp in the sense that no one of the numbers i, 7?i and 2 in N _{i, 7-i, 2} can be replaced by a larger number.     

On the number of non-isomorphic subgraphs

Let $\mathcal{K}$ be the family of graphs on ω₁ without cliques or independent subsets of sizew ₁. We prove that

1. it is consistent with CH that everyGε $\mathcal{K}$ has 2^ω many pairwise non-isomorphic subgraphs,
2. the following proposition holds in L: (*)there is a Gε $\mathcal{K}$ such that for each partition (A, B) of ω₁ either G?G[A] orG?G[B],
3. the failure of (*) is consistent with ZFC.