A Note on Strongly Regular Self-complementary Graphs

Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 = x^2 ＋ y^2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k ＋ 1 orders.

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv∈ E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by X＇Aa（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.

Strong Edge Coloring of Outerplane Graphs with Independent Crossings

The strong chromatic index of a graph is the minimum number of colors needed in a proper edge coloring so that no edge is adjacent to two edges of the same color.An outerplane graph with independent crossings is a graph embedded in the plane in such a way that all vertices are on the outer face and two pairs of crossing edges share no common end vertex.It is proved that every outerplane graph with independent crossings and maximum degreeΔhas strong chromatic index at most 4Δ-6 if Δ≥4,and at most 8 ifΔ≤3.Both bounds are sharp.

On the Adjacent Strong Edge Coloring of Outer Plane Graphs

A k-adjacent strong edge coloring of graph G(V, E) is defined as a proper k-edge coloring f of graph G(V, E) such that f[u] ≠ f[v] for every uv ∈ E(G), where f[u] = {f(uw)|uw ∈ E(G)} and f(uw) denotes the color of uw, and the adjacent strong edge chromatic number is defined as x'as(G) = min{k| there is a k-adjacent strong edge coloring of G}. In this paper, it has been proved that △ ≤ x'as(G) ≤ △ + 1 for outer plane graphs with △(G) ≥ 5, and X'as(G) = △ + 1 if and only if there exist adjacent vertices with maximum degree.

On the Adjacent Strong Edge Coloring of Halin Graphs

A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.

Adjacent Strong Edge Chromatic Number of Series-Parallel Graphs

In this paper, we will study the adjacent strong edge coloring of series-parallel graphs, and prove that series-parallel graphs of △(G) = 3 and 4 satisfy the conjecture of adjacent strong edge coloring using the double inductions and the method of exchanging colors from the aspect of configuration property. For series-parallel graphs of △(G) ≥ 5, △(G) ≤ x'as(G) ≤ △(G) + 1. Moreover, x'as(G) = △(G) + 1 if and only if it has two adjacent vertices of maximum degree, where △(G) and X'as(G) denote the maximum degree and the adjacent strong edge chromatic number of graph G respectively.

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that X as ′ (G) = X t (G) for every k-regular graph G with no C 5 component (k ? 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V(G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.

A Note on Adjacent Strong Edge Coloring of K(n,m)

In this paper, we prove that the adjacent strong edge chromatic number of a graph K（n,m） is n ＋ 1, with n ≥ 2, m ≥ 1.

Strong Labelings of Linear Forests

A （p, q）-graph G is called super edge-magic if there exists a bijective function f ： V（G） U E（G） →{1, 2 p＋q} such that f（u）＋ f（v）＋f（uv） is a constant for each uv C E（G） and f（Y（G）） = {1,2,...,p}. In this paper, we introduce the concept of strong super edge-magic labeling as a particular class of super edge-magic labelings and we use such labelings in order to show that the number of super edge-magic labelings of an odd union of path-like trees （mT）, all of them of the same order, grows at least exponentially with m.

An Upper Bound for the Adjacent Vertex Distinguishing Acyclic Edge Chromatic Number of a Graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to v, where uv ∈E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ＇αα（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G（V, E） is a graph with no isolated edges, then χ＇αα（G）≤32△.