Removable edges in cycles of a <Emphasis Type="Italic">k</Emphasis>-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N _G−e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4).     

Scale Free Properties of Random <Emphasis Type="Italic">k</Emphasis>-Trees

Scale free graphs have attracted attention as their non-uniform structure that can be used as a model for many social networks including the WWW and the Internet. In this paper, we propose a simple random model for generating scale free k-trees. For any fixed integer k, a k-tree consists of a generalized tree parameterized by k, and is one of the basic notions in the area of graph minors. Our model is quite simple and natural; it first picks a maximal clique of size k + 1 uniformly at random, it then picks k vertices in the clique uniformly at random, and adds a new vertex incident to the k vertices. That is, the model only makes uniform random choices twice per vertex. Then (asymptotically) the distribution of vertex degree in the resultant k-tree follows a power law with exponent 2 + 1/k, the k-tree has a large clustering coefficient, and the diameter is small. Moreover, our experimental results indicate that the resultant k-trees have extremely small diameter, proportional to o(log n), where n is the number of vertices in the k-tree, and the o(1) term is a function of k.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

Goal-minimally <Emphasis Type="Italic">k</Emphasis>-elongated graphs

Let k be an integer. A 2-edge connected graph G is said to be goal-minimally k-elongated (k-GME) if for every edge uv ∈ E(G) the inequality d _G−uv (x, y) > k holds if and only if {u, v} = {x, y}. In particular, if the integer k is equal to the diameter of graph G, we get the goal-minimally k-diametric (k-GMD) graphs. In this paper we construct some infinite families of GME graphs and explore k-GME and k-GMD properties of cages. This research was supported by the Slovak Scientific Grant Agency VEGA No. 1/0406/09.     

On the Structure of Contractible Vertex Pairs in Chordal Graphs

An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.     

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

The contractible subgraph of 5-connected graphs

An edge e of a k-connected graph G is said to be k-removable if G — e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction results still in a k-connected graph. A k-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k-connected. In this paper, we show that there is a contractible subgraph in a 5-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally 5-connected graph is contained in some triangle.     

Partitioning a graph into defensive <Emphasis Type="Italic">k</Emphasis>-alliances

A defensive k-alliance in a graph is a set S of vertices with the property that every vertex in S has at least k more neighbors in S than it has outside of S. A defensive k-alliance S is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive k-alliances. The (global) defensive k-alliance partition number of a graph Θ = (V, E), (ψ _k ^gd (Γ)) ψ _k ^d (Γ), is defined to be the maximum number of sets in a partition of V such that each set is a (global) defensive k-alliance. We obtain tight bounds on ψ _k ^d (Θ) and ψ _k ^gd (Γ) in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of Γ₁ × Γ₂ into (global) defensive (k ₁ + k ₂)-alliances and partitions of Γ _i into (global) defensive k _i -alliances, i ∈ {1, 2}.     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003     

Bounds on the <Emphasis Type="Italic">k</Emphasis>-tuple domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A vertex of a graph G dominates itself and all vertices adjacent to it. A subset S ⊆ V (G) is a k-tuple dominating set of G if each vertex of V (G) is dominated by at least k vertices in S. The k-tuple domatic number of G is the largest number of sets in a partition of V (G) into k-tuple dominating sets.     

On κ—ordered Graphs Involved Degree Sum

A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G）≥3κ-1/2 or δ（G）≥5κ-4.Several known results are generalized.     

Orientations Making <Emphasis Type="Italic">k</Emphasis>-Cycles Cyclic

We show that the minimum number of orientations of the edges of the n-vertex complete graph having the property that every triangle is made cyclic in at least one of them is \(\lceil \log _2(n-1)\rceil \). More generally, we also determine the minimum number of orientations of \(K_n\) such that at least one of them orients some specific k-cycles cyclically on every k-element subset of the vertex set. Though only formally related, the questions answered by these results were motivated by an analogous problem of Vera T. Sós concerning triangles and 3-edge-colorings. Some variants of the problem are also considered.     

<Emphasis Type="Italic">k</Emphasis>-noncrossing and <Emphasis Type="Italic">k</Emphasis>-nonnesting graphs and fillings of ferrers diagrams

We give a correspondence between graphs with a given degree sequence and fillings of Ferrers diagrams by nonnegative integers with prescribed row and column sums. In this setting, k-crossings and k-nestings of the graph become occurrences of the identity and the antiidentity matrices in the filling. We use this to show the equality of the numbers of k-noncrossing and k-nonnesting graphs with a given degree sequence. This generalizes the analogous result for matchings and partition graphs of Chen, Deng, Du, Stanley, and Yan, and extends results of Klazar to k > 2. Moreover, this correspondence reinforces the links recently discovered by Krattenthaler between fillings of diagrams and the results of Chen et al.     

High Connectivity Keeping Sets In <Emphasis Type="Italic">n</Emphasis>-Connected Graphs

It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected.     

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

Optimal (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) visual cryptographic schemes for general <Emphasis Type="Italic">k</Emphasis>

In (k, n) visual cryptographic schemes (VCS), a secret image is encrypted into n pages of cipher text, each printed on a transparency sheet, which are distributed among n participants. The image can be visually decoded if any k(≥2) of these sheets are stacked on top of one another, while this is not possible by stacking any k − 1 or fewer sheets. We employ a Kronecker algebra to obtain necessary and sufficient conditions for the existence of a (k, n) VCS with a prior specification of relative contrasts that quantify the clarity of the recovered image. The connection of these conditions with an L ₁-norm formulation as well as a convenient linear programming formulation is explored. These are employed to settle certain conjectures on contrast optimal VCS for the cases k = 4 and 5. Furthermore, for k = 3, we show how block designs can be used to construct VCS which achieve optimality with respect to the average and minimum relative contrasts but require much smaller pixel expansions than the existing ones.     

Interval <Emphasis Type="Italic">k</Emphasis>-Graphs and Orders

An interval k-graph is the intersection graph of a family of intervals of the real line partitioned into k classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k =?2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k >?2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder.     

On <Emphasis Type="Italic">k</Emphasis>-th Power of Upper Bound Graphs

We consider k-th power of upper bound graphs. According to the characterization of upper bound graphs, we obtain a characterization of k-th power of upper bound graphs. That is, for a connected upper bound graph G, G^k is an upper bound graph if and only if for any pair of A^k -simplicial vertices s₁, s₂ such that , there exists a G^k -simplicial vertex s satisfying the conditions: and . Furthermore we also get some properties on squares of upper bound graphs.AMS Subject Classification: 05C62.     

The <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-dominating set of the graph G is a subset D of V (G) such that every vertex of V (G)-D is adjacent to at least k vertices in D. A k-domatic partition of G is a partition of V (G) into k-dominating sets. The maximum number of dominating sets in a k-domatic partition of G is called the k-domatic number d _k (G). In this paper, we present upper and lower bounds for the k-domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical domatic number d(G) = d ₁(G).